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

 

알고리즘 분류: 정렬, 값/좌표 압축

문제 링크: https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

 

 

 

【 풀이 】

범위 내의 중복된 값을 뒤로 보내주는 unique 함수와,

이진 탐색 기반으로, 찾으려는 값보다 크거나 같은 숫자가 몇 번째 인덱스에서 처음 나오는지를 알려주는 lower_bound 함수를 이용하여 해결했다.

 

풀이 과정은 다음과 같다.

 

1. 우선 원본 좌표를 저장한 벡터와 원본 좌표를 복사한 벡터 두 가지를 선언한다.
2. unique 함수와 lower_bound 함수는 정렬되어 있을 때 효과를 볼 수 있으므로 복사한 벡터를 sort 함수로 정렬한다.
3. unique 함수를 사용했을 때는 뒤로 보낸 중복 원소 중 첫번째 원소의 주소를 반환하므로, 복사한 벡터에서 erase 함수를 이용하여 cpy.end() 까지 삭제해 준다.
4. 여기서, 복사한 벡터의 각 인덱스는, 인덱스에 해당하는 값의 압축 좌표에 해당된다.
5. 즉 lower_bound 를 이용하여 원본 벡터의 각 인덱스 값에 맞게 찾아준 후, 압축 좌표로 바꿔준다.

 

 

【 코드 】

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

vector<long long>coord;
vector<long long>cpy;

int main() {
	int N;
	cin >> N;

	// 1번 과정
	for (int i = 0; i < N; i++) {
		int val;
		cin >> val;
		coord.push_back(val);
		cpy.push_back(val);
	}

	// 2번 과정
	sort(cpy.begin(), cpy.end());
    
	// 3번 과정
	cpy.erase(unique(cpy.begin(), cpy.end()),cpy.end());
	
    	// 4, 5번 과정
	for (int i = 0; i < N; i++) {
		auto val = lower_bound(cpy.begin(), cpy.end(), coord[i])-cpy.begin();
		coord[i] = val;
	}
	for (int i = 0; i < N; i++) {
		cout << coord[i] << " ";
	}

	return 0;
}