https://www.acmicpc.net/problem/18870
입력받은 좌표를 정렬한 후, 한 좌표에 대해서 그것보다 작은 값을 가지는 좌표의 개수를 구해야 한다.
그런데 입력받은 순서대로 좌표 압축 결과를 출력해야 하므로, 입력받은 순서를 저장해야 한다.
따라서 원본 벡터 A와 정렬된 벡터 B 두 가지를 사용한다.
정렬된 벡터 B에서는 중복된 값을 삭제하면, B[i]의 좌표 압축 결과가 인덱스 i와 같다.
lower_bound
함수를 이용하여 원본 벡터 A에서 가리키는 좌표값 A[j]와 동일한,
정렬된 벡터에서의 좌표값 B[i]를 구할 수 있고, 이것의 인덱스 i도 구할 수 있다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n;
cin >> n;
vector<int> v1(n);
for(int i=0; i<n; i++) cin >> v1[i];
vector<int> v2 = v1;
sort(v2.begin(), v2.end());
v2.erase(unique(v2.begin(), v2.end()), v2.end());
for(int i=0; i<n; i++) {
cout << lower_bound(v2.begin(), v2.end(), v1[i]) - v2.begin() << " ";
}
return 0;
}