[백준] 18870번 : 좌표 압축

문제

 

---

풀이

 

예제 입력1을 오름차순 정렬해보자

-10

-9

2

4

4

 

여기서 중복을 제거하면

-10

-9

2

4

 

이 배열의 인덱스는 당연히 왼쪽에서부터 0, 1, 2, 3이다.

그리고 이건 각 숫자에 대해 해당 숫자보다 작은 수의 개수가 된다.

---

소스코드

 

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long input;
    vector<long long> arr, sort_arr;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> input;
        arr.push_back(input); //원래 배열
    }
    sort_arr = arr;
    sort(sort_arr.begin(), sort_arr.end()); //정렬
    sort_arr.erase(unique(sort_arr.begin(), sort_arr.end()), sort_arr.end()); //중복 제거
    for (int i = 0; i < N; i++) //lower bound의 index 반환
        cout << lower_bound(sort_arr.begin(), sort_arr.end(), arr[i]) - sort_arr.begin() << ' ';
}

처음엔 find 함수를 사용했는데 시간초과가 나와서 이분 탐색으로 진행하는 lower_bound 함수를 사용했다.