'좌표 압축 기법'이란?
여러분은 배열 $A_n$을 이용해 문제를 해결하고자 한다.
그런데 배열의 수의 범위($Min(A_n)$ ~ $Max(A_n)$)가 너무 커서 주어진 제한 시간을 맞추기 힘들다.
수의 값과 무관하게 숫자 간의 대소 관계만 필요하다면, 수의 범위를 줄일 수 있을까?
$A_n$의 길이가 수의 범위보다 작다면, 좌표 압축 기법을 이용해 수의 범위를 줄일 수 있다.
어렵게 생각할 필요 없이, 숫자를 크기 순으로 정렬해 각각의 수에 0부터 숫자를 하나씩 매겨주면 된다.
예를 들어, $[-7, 100000, 876]$이 있다고 해보자.
크기 순으로 숫자를 매겨주면 $[0, 2, 1]$이 된다. 이렇게 수의 범위를 줄이는 테크닉을 좌표 압축이라고 한다.
구현해보기
좌표 압축은 아래와 같은 단계로 진행한다.
- 원본 배열에서 중복값을 제거한 새로운 배열을 만든다,
- 1에서 생성된 배열을 오름차순 정렬한다.
- 원본 배열의 각 원소에 대해, 2에서 생성된 배열에서의 Index를 찾는다.
단계별로 코드를 작성해보자.
중복 제거
배열을 압축한 후 적용하려는 알고리즘에 따라 해당 단계가 필요하지 않을 수도 있다.
이 단계는 압축 전의 값이 동일한 원소들이 압축 후에도 동일한 값을 갖도록 하기 위해 진행한다.
즉, $[100, -100, 100]$에서 100을 모두 1로 변환해 $[1, 0, 1]$이 될 수 있도록 미리 작업해두는 것이다.
파이썬에서는 중복을 허용하지 않는 자료 구조인 set(집합)이 있으므로, 아주 쉽게 구현할 수 있다.
unique_An = set(An)
정렬
그냥 sort를 사용해주면 된다. (set을 굳이 list로 변환한 후 정렬하지 않아도 된다.)
sorted_An = sorted(unique_An)
압축된 값 부여하기
이 단계에서는 이진 탐색(bisect_left), 닥셔너리(dict), 순서가 있는 딕셔너리(OrderedDict) 등 다양한 방법을 사용할 수 있다.
이번에는 파이썬만의 강력한 문법 기능을 활용해 그냥 딕셔너리로 구현해보자.
이 단계에서 해야하는 일은 원래 배열의 각 원소를 정렬된 배열에서의 Index로 바꿔줘야 한다.
그러기 위해 기존 원소를 Key, 정렬된 배열의 Index를 Value로 가지는 딕셔너리를 만들어주자.
# 1. Using dictionary comprehension
index_dict = {sorted_An[i] : i for i in range(len(sorted_An))}
# 2. Using zip
index_dict2 = dict(zip(sorted_An, range(len(sorted_An))))
index_dict와 index_dict2의 결과는 동일하므로, 편한 방법을 사용하면 된다.
여기까지 완료했다면, 바로 우리가 원하는 좌표 압축 배열을 구해줄 수 있다.
result = [index_dict[i] for i in An]
최종 코드
input()
An = list(map(int, input().split()))
sorted_An = sorted(set(An))
index_dict = dict(zip(sorted_An, range(len(sorted_An))))
print(*[index_dict[i] for i in An])백준 18870번(좌표 압축)의 정답 코드이다.
시간 복잡도는 정렬에 의해 $O(Nlog_2N)$이다.
관련 문제 (BOJ)
좌표 압축은 주로 스위핑이나 세그먼트 트리 사용시 숫자의 범위를 줄여주기 위해 사용된다.
- [18870] 좌표 압축: 좌표 압축을 그래도 하면 되는 문제. 바로 위의 코드를 넣으면 풀린다..
- [18869] 멀티버스 Ⅱ: 좌표 압축만을 활용하는 문제.
- [20440] 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1: 좌표 압축 + 누적합(imos법)
- [5419] 북서풍: 스위핑 + 세그먼트 트리 (feat. 좌표 압축)
