[baekjoon 18870] 좌표 압축 - 정렬, 값 압축 (C++)

www.acmicpc.net/problem/18870

18870번: 좌표 압축

여기서 압축은 전체 좌표에서 해당 좌표값보다 작은 좌표의 개수(중복 제거)로 줄이는 것을 의미한다.

그래서 벡터를 두 개 이용해서 하나의 벡터에 중복된 값을 제거, 정렬을 해준 후, 이분 탐색을 통해 개수를 구했다.

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

vector<int> v, v1;
int N, num;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		v.push_back(num);
		v1.push_back(num);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	for (int i = 0; i < v1.size(); i++) {
		int start = 0;
		int end = v.size();
		while (1) {
			int mid = (start + end) / 2;
			if (v[mid] == v1[i]){
				cout << mid << " ";
				break;
			}
			else if (v[mid] > v1[i]) {
				end = mid - 1;
			}
			else if (v[mid] < v1[i]) {
				start = mid + 1;
			}
		}
	}
}

unique 함수를 배워서 사용해보았다.

v.erase(unique(v.begin(), v.end()), v.end()); 를 해주면 벡터 내에서 중복된 값을 제거해준다.