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

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;
}