큰 값을 작은 값으로 매핑하기 : 좌표 압축 알고리즘

입력의 범위가 터무니 없이 크다면

입력으로 범위가 [0, 1000000000]인 값이 1,000개 들어올 때 입력 값을 인덱스로 하는 배열이 필요하다면 아래와 같은 방법을 사용할 수 있을까? 아니다, 배열의 메모리만 해도 4 * 10억 byte = 4GB로 메모리가 부족하다.

int index[1000000000];
int main(){
    for(int i = 0; i < 1000; i++){
        int var;
        cin >> var;
        index[var] = 1;
    }
}

좌표 압축 알고리즘

입력 값의 범위가 10억이지만, 입력의 개수는 1,000개 이므로 배열에 쓸모없는 공간이 너무 많다. 예를 들어 공차가 100인 값이 1,000개 들어온다고 해도 각 입력 값 사이의 빈 공간이 99개나 있는 격이다. 배열 사이의 빈 공간을 줄여서 값들에 새로운 인덱스를 부여해보자.

빈 공간 줄이기

먼저 입력 값을 그냥 배열에 순서대로 받아보자.

vector<int> arr;
for(int i = 0; i < 1000; i++) {
    int input;
    cin >> input;
    arr.push_back(input);
}

그 후 그림처럼 오름차순으로 빈 공간이 없이 서로 붙여야 하므로 정렬을 하여 오름차순으로 만들어주자.

sort(arr.begin(), arr.end());

배열에 동일한 수가 있을 수도 있다. 따라서 중복된 수를 제거해야 한다.

arr.erase(unique(arr.begin(), arr.end()), arr.end());

이제 빈 공간이 없이 오름차순으로 arr가 만들어졌다. 이제 원하는 값의 인덱스를 어떻게 얻을 수 있을까? arr배열은 중복 없는 오름차순으로 정렬되어 있으므로 이분 탐색을 수행하면 \(log(n)\)에 원하는 값의 위치를 찾을 수 있다.

int search = 123123;
int index = lower_bound(arr.begin(), arr.end(), search) - arr.begin();

map을 이용한 좌표 압축

map을 이용해 실시간으로 값을 입력받으며 좌표를 압축하는 방법도 있다. 

map<string, int> idx;
int numbering(const string& str) {
    if (idx.find(str) == idx.end()) idx[str] = (int)idx.size();
    return idx[str];
}