좌표 압축: 순서는 남기고 값의 크기는 줄이기

값이 1조여도 서로 다른 값이 몇 개 없다면, 그 값들을 작은 배열의 인덱스로 바꿀 수 있습니다. 단, 압축한 인덱스는 순위를 나타낼 뿐 원래 거리를 나타내지는 않습니다. 이 구분을 손으로 확인하고, 중복과 음수가 있는 입력을 실행합니다.

좌표 압축은 값의 크기 자체는 크지만 서로 다른 값의 개수가 작을 때, 값을 0..m-1 또는 1..m 범위의 인덱스로 바꾸는 기법입니다. Fenwick Tree, Segment Tree, 스위프 라인, 오프라인 쿼리에서 자주 함께 쓰입니다.

값은 크지만 서로 다른 값의 개수는 작을 때

예를 들어 좌표가 1, 1,000,000,000, 500,000,000처럼 크면 좌표를 그대로 배열 인덱스로 쓸 수 없습니다. 하지만 실제로 등장한 값이 3개뿐이라면, 정렬 순서만 유지해서 아래처럼 바꿀 수 있습니다.

원래 값: 1, 500000000, 1000000000
압축 값: 0, 1, 2

중요한 것은 대소 관계를 보존한다는 점입니다. 원래 값이 작을수록 압축 인덱스도 작습니다.

정렬 + unique

먼저 모든 값을 한 벡터에 모아 정렬하고 중복을 제거합니다.

코드 환경: 일반 C++17 학습용. 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 공통 코드와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

vector<int> values = a;
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());

이제 values[i]는 압축 인덱스 i가 나타내는 원래 값입니다.

lower_bound로 압축 인덱스 만들기

원래 값 x의 압축 인덱스는 lower_bound로 찾습니다.

int compress(const vector<int>& values, int x) {
    return lower_bound(values.begin(), values.end(), x) - values.begin();
}

모든 x가 values에 들어 있다는 전제가 있어야 합니다. lower_bound는 없는 값에도 삽입 위치를 반환하므로, 끝에 도달했는지와 실제 값이 x인지 구분합니다. 온라인으로 새로운 값이 중간에 들어오는 문제라면, 먼저 모든 쿼리를 읽어 등장 가능한 값을 모으는 오프라인 처리가 필요할 수 있습니다.

압축부터 복원까지 따라가기

정렬·중복 제거·순위 매핑 실험

입력 [-10, 100, -10, 7, 100, 8]을 정렬하면 [-10, -10, 7, 8, 100, 100], 중복을 없애면 [-10, 7, 8, 100]입니다. 원래 순서에서 각각의 위치를 찾으면 [0, 3, 0, 1, 3, 2]가 됩니다. 같은 값은 같은 인덱스를 공유하지만, 입력 원소 자체를 삭제하지는 않습니다.

그림 크게 보기

작은 순위만 저장해도 되는 빈도·대소 비교와, 원래 간격이 필요한 길이·넓이 계산을 구분하세요. 압축한 두 구간을 각각 길이 1로 세면 전체 길이를 2로 계산하지만, 원래 [10,100)의 길이는 90입니다.

정수 범위도 함께 옮겨야 합니다. 위 개념 조각은 vector<int>이지만 아래 연습은 절댓값 10^12까지 받습니다. 다운로드 예제에서는 원본 값과 중복 제거 배열을 long long으로, 압축 인덱스를 int로 저장합니다.

압축한 값을 빈도 인덱스로 쓰기

역전쌍은 i < j인데 a[i] > a[j]인 쌍입니다. 왼쪽부터 읽으면서 Fenwick Tree에 값별 등장 횟수를 저장하면 셀 수 있습니다.

현재 값의 0-based 압축 인덱스가 r이고 앞에서 i개를 읽었다면, 1-based Fenwick에서 새 역전쌍은 i - prefixSum(r + 1)개입니다. prefixSum(r + 1)는 현재 값 이하의 개수이므로 같은 값끼리는 세지 않습니다. 답에 더한 뒤 add(r + 1, 1)로 빈도를 1 올립니다.

[3, 1, 3, 2]를 읽으면 새로 생기는 쌍은 차례로 0, 1, 0, 2개, 총 3개입니다. 압축 순위와 Fenwick 인덱스 사이의 +1을 질의와 갱신 양쪽에 적용합니다.

구간 좌표 압축에서 주의할 점

원문의 구조 그림 크게 보기

[10,20)과 [20,100)은 압축 후 각각 한 칸이지만 길이는 10과 80입니다. 길이·넓이를 합산할 때는 원본 좌표 간격을 함께 저장합니다.

구간 [l, r]을 다룰 때는 문제의 의미에 따라 r + 1도 같이 넣어야 할 수 있습니다. 예를 들어 차분 배열처럼 [l, r]에 더하고 r + 1에서 빼는 방식이면 r + 1 좌표가 반드시 필요합니다.

또 면적이나 길이를 계산하는 문제에서는 압축 인덱스 차이가 실제 거리와 다릅니다. 이때는 values[i + 1] - values[i]처럼 원래 좌표 간격을 곱해야 합니다.

시간 복잡도

작업	시간
값 수집	O(n)
정렬과 중복 제거	O(n log n)
값 하나 압축	O(log n)
unordered map으로 미리 매핑	평균 O(1)
메모리	O(n)

로컬 연습: 중복과 음수가 있는 값의 순위

서로 다른 값을 정렬한 뒤 각 원소를 그 배열에서의 0-based 위치로 바꾸세요. 압축값의 차이가 실제 거리라고 가정하지 않습니다.

입력: N과 길이 N의 정수 배열. 1 <= N <= 200000, |a[i]| <= 10^12입니다.

출력: 첫 줄에 서로 다른 값의 수, 둘째 줄에 원래 순서의 압축값, 셋째 줄에 정렬된 서로 다른 원본 값을 출력합니다.

예시

6
-10 100 -10 7 100 8

4
0 3 0 1 3 2
-10 7 8 100

확인 방법: 원본의 같음·대소 관계가 압축값에서도 유지되고 coords[rank[i]]가 a[i]로 복원되는지 확인합니다. 전부 같은 값, 감소 순서, 64비트 값을 검사합니다.

완성 파일로 실행하고 확인하기

C++17 전체 예제 내려받기

c++ -std=c++17 -O2 coordinate-compression.cpp -o lesson
./lesson < input.txt

원본 값은 64비트 정수, 순위는 0-based입니다. 위 예제의 세 줄을 그대로 출력합니다. 파일은 정렬과 중복 제거, 순위 조회를 compressValues 함수로 묶고 main까지 포함합니다.

입력 [-1000000000000, 1000000000000, -1000000000000]이면 서로 다른 값은 2개, 순위는 [0,1,0]입니다. 값이 모두 같으면 모두 0이 됩니다. 출력한 원본 값 배열 coords를 사용해 모든 위치에서 coords[rank[i]] == input[i]가 성립하는지 확인하세요. 이 검사는 순서와 중복 처리를 함께 확인합니다.

Fenwick Tree와 연결할 때는 압축 순위에 1을 더해 호출합니다. 역전쌍에서 같은 값을 제외하려면 ‘현재 값 이하’의 개수를 빼야 한다는 점도 확인하세요. 압축이 실제 값의 중복까지 없애 주는 것은 아닙니다.