좌표 압축 - 알고리즘카

수열이나 다른 객체들의 시퀀스를 연속된 정수 구간으로 변환하는 것이 유용한 경우가 많습니다. 예를 들어, 그 원소들을 배열이나 다른 자료 구조의 인덱스로 사용하려는 경우가 그렇습니다.

이 문제는 집합의 원소에 번호를 매기는 것과 동등하며, 이는 해시 테이블을 사용하여 $O(n)$에 수행할 수 있습니다:

vector<int> compress(vector<int> a) {
    unordered_map<int, int> m;

    for (int &x : a) {
        if (m.count(x))
            x = m[x];
        else
            m[x] = m.size();
    }

    return a;
}

원소에는 수열에 처음 등장한 순서대로 번호가 부여됩니다. 더 작은 원소에 더 작은 번호를 부여하여 순서를 유지해야 한다면 문제가 조금 더 어려워지며, 여러 가지 방법으로 해결할 수 있습니다.

다른 방법으로, 배열을 정렬한 다음 해시 테이블을 사용하여 배열을 두 번 순회할 수도 있습니다. 첫 번째 순회에서는 해시 테이블을 채우고, 두 번째 순회에서는 배열 자체를 압축합니다:

vector<int> compress(vector<int> a) {
    vector<int> b = a;
    sort(b.begin(), b.end());

    unordered_map<int, int> m;

    for (int x : b)
        if (!m.count(x))
            m[x] = m.size();

    for (int &x : a)
        x = m[x];

    return a;
}

또한 정렬된 배열에서 중복된 원소를 (선형 시간에) 제거한 다음, 이를 이용해 원래 배열의 각 원소의 인덱스를 이진 탐색으로 찾을 수도 있습니다:

vector<int> compress(vector<int> a) {
    vector<int> b = a;

    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    for (int &x : a)
        x = int(lower_bound(b.begin(), b.end(), x) - b.begin());

    return a;
}

두 방법 모두 $O(n \log n)$의 시간에 동작합니다. 더 마음에 드는 쪽을 사용하십시오.