백준 s2 18870 좌표 압축 c++

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

18870번: 좌표 압축

 

문제

X_i` = X_i보다 작은, 중복되지 않은, 다른 원소의 개수

 

풀이

배열을 두 번씩 돌리면서 각각 X_j의 개수를 세는 방법도 있지만 N <= 10^6이므로, 시간초과가 난다. O(n^2)

 

X_i보다 작은 원소의 개수이므로, 정렬 후 이분 탐색의 lower_bound를 이용하여 index의 차이를 구하는 방법을 생각할 수 있다. -> O(NlogN)

 

코드

 

/*boj s2 18870 좌표 압축*/
#include <algorithm>
#include <iostream>
#include <vector>
#define MAXN 1000010
using namespace std;

int N;
int input[MAXN];
vector<int> arr;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> input[i];
        arr.push_back(input[i]);
    }
    sort(arr.begin(), arr.end());
    arr.erase(unique(arr.begin(), arr.end()), arr.end());

    for (int i = 0; i < N; i++) {
        cout << lower_bound(arr.begin(), arr.end(), input[i]) - arr.begin() << " ";
    }
}