[Silver 2] 18870 좌표 압축

https://www.acmicpc.net/problem/18870

 

 

이 문제에서는 생소한 stl 함수를 사용하였다.

 

lower_bound 함수는 인자로 넘겨준 배열의 포인터들 사이에서 target값이 처음 나오는 인덱스의 iterator를 반환한다.

iterator를 반환하기 때문에 인덱스를 알고 싶다면 배열의 경우 배열의 첫번째 위치를 빼고 벡터의 경우 v.begin()을 빼면 된다.

 

코드에서 정렬과 같은 값을 빼준 이유는 lower_bound함수를 사용하기 위해서다.

문제의 좌표값은 수직선 상에 존재하기 때문에 같은 값은 같은 위치를 나타낸다. 

또한 인덱스를 통해 압축할 좌표의 위치를 알기 위해서는 정렬을 통해 수직선 상에 나타내야 한다.

 

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

int N;
int arr[1000001];
vector<int> v;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>N;

    int x;
    for(int i = 0;i<N;i++){
        cin>>x;
        arr[i] = x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()),v.end());
    for(int i = 0;i<N;i++){
        int target = arr[i];
        auto iter = lower_bound(v.begin(),v.end(),target);

        cout<<iter - v.begin()<<' ';
    }
}