좌표 압축 - 원소의 밀도를 높이자

스위핑이나 탐색을 하면서 어떤 범위를 전부 확인해야 한다고 해보자.

 

그런데 그 범위가 -100억 ~ 100억 이라면? 단순 선형 탐색도 시간 초과를 피하기 어려울 것이다.

 

다만 범위에 속한 원소의 개수가 충분히 작다면 각 원소의 좌표들을 원소의 개수만큼의 범위로 압축한다면 빠르게 탐색을 할 수 있다.

 

이렇게 좌표의 범위를 압축하여 원소 집합의 밀도를 높이는 기법을 좌표 압축이라고 부른다.

 

이 게시글에서는 C++의 STL로 간단하게 압축하는 방법을 알아본다.

 

방법은 아주 간단하다. 원소를 벡터로 모두 수집한 다음 std::erase와 std::unique를 이용하여 중복 원소를 모두 제거하면 index와 원소가 일대일 대응하게 되어 좌표 압축을 할 수 있다.

 

std::unique를 사용하기 위해 벡터는 정렬된 상태여야 한다는 것을 유의하라.

vector<int> crd;

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

 

이렇게 압축된 좌표는 이진탐색으로 간단히 구할 수 있다.

vector<int> crd;

inline int get_idx(int val)
{
    // 시작 index가 1일 경우에는 아래처럼 1을 더해준다.
    return (lower_bound(crd.begin(), crd.end(), val) - crd.begin()) + 1;
}

 

만약 압축된 좌표를 찾는 연산이 많으면 배열에 저장하여 시간을 절약하도록 하자.