[C++] 백준 18870번 좌표 압축

1. 문제이해

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

수직선 위에 N개의 좌표를 압축하려고 할 때,

Xi를 좌표 압축한 결괏값이 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

N개의 좌표를 입력받고, 해당 좌표들을 압축한 결과를 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

N개의 좌표들을 입력받아 해당 좌표들을 압축한 결과를 출력하는 것이 목표이다.

압축 방식은 자신보다 작은 좌표의 개수를 중복을 제외하고 세는 것이다.

 

예를 들어, 1 2 2 4 5 라는 좌표가 주어지면,

자신보다 작은 좌표의 개수를 중복을 제외하고 세어 출력하면 된다.

따라서, 압축된 결과는 0 1 1 2 3 이 된다.

해당 결과를 도출하기 위해, 필자는 아래 3단계로 나누어 압축을 진행했다.

 

1. 주어진 좌표를 오름차순으로 정렬

: 주어진 좌표값들을 오름차순으로 정렬해준다.

이때, 아래 3번에서 원래 입력받은 좌표값의 배열이 필요하므로,

좌표값을 입력받아 각기 다른 배열에 따로 저장해주기로 했다.

(복사본을 하나 생성한 것과 동일)

 

2. 중복 값을 제거

: 문제에서 자신보다 작은 좌표의 개수를 중복을 제외하고 세는 것이라고 했으므로,

오름차순으로 정렬된 배열 값에서 중복된 값을 제거한다.

 

3. 원래 입력받은 좌표값 순서대로 자신보다 작은 좌표의 갯수를 세어줌

: 기존 입력받은 배열의 첫번째 값부터 자신보다 작은 좌표의 개수를 

정렬 & 중복값이 제거된 배열에서 찾고, 해당 개수를 출력한다.

 

해당 과정에서 필자는 lower_bound() 를 사용해주었다.

lower_bound는 찾으려는 값이 배열의 몇 번째에 존재하는지 반환해주는 함수로,

lower_bound (배열, 배열의 크기, 찾으려는 값) - 배열

과 같은 형태로 사용할 수 있다.

 

 

 

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N;                  
	int tmp;
	vector<int> location;        // 입력받은 순서대로의 좌표값
	vector<int> com_location;    // 압축, 정렬된 좌표값

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		location.push_back(tmp);
		com_location.push_back(tmp);
	}

	// 1. 오름차순 정렬
	sort(com_location.begin(), com_location.end());

	// 2. 중복 값 제거
	com_location.erase(unique(com_location.begin(), com_location.end()), 
		com_location.end());

	// 3. 원래 좌표값보다 작은 값의 개수를 체크 & 출력
	for (int i = 0; i < N; i++) {
		cout << lower_bound(com_location.begin(), com_location.end(), 
			location[i]) - com_location.begin() << " ";
	}
	
	return 0;
}

2. 문제풀이에서 도출한 방식을 이용해 작성한 코드는 위와 같다.

좌표의 개수를 입력받고, 좌표값들을 입력받아 두개의 벡터에 저장한다.

( 여기서, location 은 원래 좌표의 배열값을 저장할 벡터,

com_location 은 정렬 & 중복제거를 할 벡터이다. )

 

com_location에 대해, 오름차순 정렬과 중복값을 제거한다.

이후, for문과 lower_bound 함수를 통해 com_location과 location을 비교,

원래 좌표값보다 작은 좌표의 개수를 세고, 출력한다.

 

 

---

문제에 대한 질문이나 지적 등은 언제나 감사하게 받고 있습니다.😌