[Baekjoon] 18870: 좌표 압축 - (C3, S2) std::set, std::unordered_map

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

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

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

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

18870번: 좌표 압축

 

클래스 3쯤 되니 항상 시간복잡도에 대한 생각을 하지 않을 수 없다. 단순하게 생각하면, 좌표를 입력받고, 모든 좌표를 탐색해 X_i보다 작은 좌표의 개수를 계산하는 아주 단순무식한 방법이 있다. 하지만 이런식으로 코딩을 해서야 되겠는가. 

 

1. vector로 좌표를 입력받는다.

2. 동시에, set에 좌표를 입력받는다. 

3. map에 set의 좌표 값과 인덱스를 매핑한다.

 

set은 내부적으로 오름차순 정렬하고, 중복을 허용하지 않는다. 다음과 같이 예제를 확인해보자. 

 

2 4 -10 4 -9 의 중복을 제거하고 오름차순 정렬하면 -10 -9 2 4 가 된다. 

여기서 X'_i, 즉 2보다 작은 좌표 개수는 2개로, 정렬된 배열에서 X_i의 인덱스가 된다. 

 

때문에 set을 이용하면 중복을 제외하고 정렬하는 작업이 수월하다. 다만, vector든 set이든 특정 요소의 위치를 반환하기 위해서는 반복자를 반환해 별도의 처리가 필요하다. 이를 빠르게 처리하기 위해 map을 이용한다. map에 set의 좌표에 해당하는 인덱스를 지정해둔다. 

 

#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
using namespace std;

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

    int N, x;
    cin >> N;

    vector<int> coord;
    coord.reserve(N); // O(1)
    set<int> unique_coord;
    unordered_map<int, int> idx_map;

    for (int i = 0; i < N; i++)
    {
        cin >> x;
        coord.push_back(x); // O(1)
        unique_coord.insert(x); // O(log n)
    }

    int idx = 0;
    for (const auto &e : unique_coord)
        idx_map[e] = idx++;

    for (int i = 0; i < N; i++)
        cout << idx_map[coord[i]] << " ";

    return 0;
}

시간복잡도를 최소화하기 위해 vector은 다음과 같이 연산을 수행한다. 

• 메모리 재할당이 필요 없을 경우, reserve(n)의 시간 복잡도는 O(1)이다. 
• push_back()의 시간 복잡도는 O(1)이다. (빈 메모리 공간, size가 있을 경우)

set의 insert()의 시간복잡도는 O(log n)이다. n번 루프를 반복하므로, 삽입 연산의 시간복잡도는 O(n log n)이다. 

 

그리고 map에 인덱스를 할당한 후, 출력하면 끝.