좌표 압축

수의 범위가 매우 큰 상황에서 수의 값에 무관하게 좌표들 사이의 대소만 알면 될 때, 좌표 압축을 이용하면 수의 범위를 줄일 수 있다.

 

1. 좌표 압축을 할 배열을 임시의 배열에 중복이 없고 정렬된 상태로 만들어 놓는다.

2. 압축할 배열의 각 수들이 임시의 배열에 몇 번째 인덱스에 해당하는 수인지 찾으면 된다. 임시의 배열은 정렬된 상태이기 때문에 이분 탐색을 이용하여 O(logN)에 찾을 수 있다.

 

C++에서 좌표 압축을 구현할 때에는 주로 std::sort, std::unique 함수로 1번을 수행하고, std::lower_bound 함수를 이용하여 2번을 수행한다.

가지고 있는 모든 수의 값을 저장한 임시의 배열을 정렬한 후 unique 함수를 이용하여 중복되는 수를 모두 제거하고, lower_bound를 이용하여 임시의 배열의 몇 번째 인덱스에 있는지 확인하면 쉽고 빠르게 좌표 압축을 할 수 있다.

예시

http://icpc.me/18870

18870번: 좌표 압축

위의 설명만으로 구현을 하지 못하겠다면 위 문제의 코드를 보고 이해해보자.

코드

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int arr[1000006];
vector<int> tmp;

int main() {
    int N; scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", arr + i);
        tmp.push_back(arr[i]);
    }
    sort(tmp.begin(), tmp.end());
    tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
    // std::unique: 중복되는 수들을 vector의 뒤로 옮기고, 그 수들의 시작 이터레이터를 리턴
    for (int i = 0; i < N; i++) {
        int idx = lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();
        printf("%d ", idx);
    }
}