Coordinate Compression

좌표 압축은 주어진 좌표(데이터)들을 더 작은 범위로 변환하는 기법입니다. 데이터를 압축해서 용량을 줄이려면 필연적으로 어떤 정보의 손실이 발생합니다. 그래서 손실되는 정보가 필요하지 않은 경우 좌표 압축을 고려해볼 수 있습니다. 좌표 압축은 하나의 주요한 알고리즘이라고 하기에는 너무 작지만, 다른 알고리즘이나 자료구조를 활용하기 전에 전처리 단계로 사용되는 경우가 많습니다.

작동방식

좌표 압축은 데이터의 상대적인 순서만 유지한 채 작은 범위로 변환하는 알고리즘입니다. 예를 들어, 다음과 같은 좌표들이 있다고 가정해봅시다.

[100, 500, 200, 3000, 150]

이 좌표들의 정확한 값은 필요하지 않지만 대소 관계만 필요한 경우, 좌표 압축을 통해 다음과 같이 변환할 수 있습니다.

[1, 3, 2, 5, 4]

마치 각 값의 순위를 나타내는 것과 비슷합니다. 정확한 값 자체는 손실되었지만 값들 사이의 대소 관계는 유지되었습니다. 그리고 100~3000 사이의 범위에 있던 값들이 1~5 사이의 작은 범위로 압축되었습니다. 이렇게 좌표 압축은 넓은 범위에 퍼져있는 데이터를 연속된 더 작은 범위로 변환하여 공간을 줄이는 방법입니다. 정확한 값이 필요한 경우 사용할 수 없지만 대소 관계만 필요한 경우 매우 유용합니다.

좌표 압축은 다음과 같은 단계로 수행됩니다.

입력 : 원본 데이터를 입력받으면서 인덱스와 같이 저장합니다. (값, 인덱스) 형태로 저장합니다.
정렬 : 값을 기준으로 데이터를 정렬합니다. 값이 작을 수록 앞에 오도록 정렬합니다.
압축 : 정렬된 데이터를 순회하면서 새로운 좌표 값을 할당합니다. 맨 앞에 있는 가장 작은 값은 1, 그 다음 값은 2와 같이 할당합니다. 중복된 값이 있는 경우에는 같은 좌표 값을 할당합니다.
복원 : 압축된 좌표 값을 원래 인덱스에 맞게 복원합니다. 인덱스를 기준으로 다시 정렬하면 됩니다. 구현을 편리하게 하기 위해 인덱스와 값을 스왑한 후 정렬하는 방법도 있습니다.

예제 코드

18870번: 좌표 압축 문제를 예시로 설명하겠습니다. \( N \)개의 정수 \( x_i \)가 주어질 때 좌표 압축을 수행한 결과를 출력하는 문제입니다.

#include <bits/stdc++.h>

using namespace std;
void fio() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); }

int main() {
    fio();

    int n; cin >> n;
    pair<int, int> a[n];

    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }

    sort(a, a + n);

    int prev = 1e9 + 1;
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (prev != a[i].first)
            idx++;

        prev = a[i].first;
        a[i].first = idx;
        swap(a[i].first, a[i].second);
    }

    sort(a, a + n);
    for (int i = 0; i < n; i++)
        cout << a[i].second << ' ';
}