(매일 BOJ) C++ 18870번 좌표압축

이번 문제는 18870번 좌표압축이다.

문제 설명

N개의 정수가 주어진다. 각 정수에 대해, 해당 값보다 작은 서로 다른 값의 개수를 출력하라.
즉, 배열 내 모든 값을 0부터 시작하는 순위(rank)로 압축한 결과를 출력하면 된다.

단, 입력되는 정수의 범위는 최대 ±10⁹이므로, 단순하게 배열로 인덱싱할 수 없다.
따라서 좌표 압축(Coordinate Compression) 기법을 사용한다.

접근법

  핵심 아이디어

• 값 자체가 아니라 값의 상대적인 순서만 중요하다.
• 중복된 값은 같은 압축값을 가져야 한다.
• 압축값은 해당 값이 정렬된 배열에서 몇 번째에 위치하는지로 정의된다.

  좌표 압축 알고리즘 (O(N log N))

1. 원본 배열을 복사하고 정렬한다.
2. 정렬된 배열에서 중복을 제거한다.
3. 각 원소의 값을 압축된 순위로 매핑한다.
4. 원래 배열의 각 원소를 압축값으로 변환하여 출력한다.

작성코드

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    int N;
    cin >> N;
    vector<int> v;

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

    set<int> s;
    for(int i : v){
        s.insert(i);
    }

    vector<int> set_v;
    for(int i : s){
        set_v.push_back(i);
    }

    unordered_map<int, int> compressed;
    for (int i = 0; i < set_v.size(); i++){
        compressed[set_v[i]] = i;
    }

    for(int i : v){
        cout << compressed[i] << ' ';
    }
}