문제 링크

조건

2초
512MB

문제

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

1 ≤ N ≤ 1,000,000
-10^9 ≤ Xi ≤ 10^9

입력

첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

접근

좌표 Xi를 모두 정렬 시키기에는 Xi의 범위가 너무 크다.
예제 입력을 보면 좌표 압축 결과 가장 작은 좌표를 0으로 잡고 그 다음 좌표로 1씩 커지는 규칙임을 알 수 있다.

즉, N개의 좌표를 배열로 입력 받아 sort()한 뒤, 본래 순서인 값의 인덱스를 찾아 출력하면 된다.

중복되는 좌표는 한번만 입력 해주어야 나중에 정렬할 때 정렬된 배열의 인덱스가 하나로 나올 수 있다. (중복 좌표를 제거해야 함)

for 문으로 중복을 찾아가며 입력을 하자니 시간 복잡도가 O(n* n)으로 너무 커,
c++ 내장 함수를 찾아보게 되었다.

풀이

1. unique() 한뒤, erase()하여 중복을 제거한다.
2. lower_bound()로 인덱스를 찾는다.

인덱스를 찾을때 find를 떠올렸었는데 find는 시간 복잡도가 O(n)이라 시간초과가 난다. 따라서 이진탐색인 lower_bound()을 사용

중복제거 erase(), unique() 포스트

이진탐색 lower_bound(), 선형탐색 find() 포스트

코드

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

using namespace std;

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

    int N, num;
    cin >> N;

    vector<int> location;
    
    for(int i=0;i<N;i++){
        cin >> num;
        location.push_back(num);
    }

    vector<int> sort_location; // 정렬할 벡터 (원본 벡터를 복사하여 정렬)
    sort_location = location;

    // 오름차순 정렬
    sort(sort_location.begin(), sort_location.end());

    // 중복 제거
    sort_location.erase(unique(sort_location.begin(), sort_location.end()), sort_location.end());

    for (int i = 0; i < N; i++)
    {
        auto index = lower_bound(sort_location.begin(), sort_location.end(), location[i]);
        cout << index - sort_location.begin() << ' ';
    }

    return 0;
}

Reference

https://donggoolosori.github.io/2020/09/26/boj-18870/