[알고리즘] 백준 18870 - 좌표 압축

1. 문제

https://www.acmicpc.net/problem/18870
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

2. 입력/출력

첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

3. 풀이

unique

erase

lower_bound

찾으려는 키 값보다 크거나 같은 숫자가 몇번째로 처음 등장하는 지
조건 : 탐색 대상이 오름차순 정렬되어있어야 함

4. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main()
{
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(0);

	int n;
	cin >> n;
	vector<int> arr;

	int tmp;

	for (int i = 0; i < n; i++) {
		cin >> tmp;
		arr.push_back(tmp);
	}

	vector<int> arr2(arr);

	sort(arr2.begin(), arr2.end());
	arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());

	for (int i = 0; i < n; i++) {
		cout << lower_bound(arr2.begin(), arr2.end(), arr[i]) - arr2.begin() << ' ';
		
	}

	return 0;
}