목차
  1. '좌표 압축 기법'이란?
  2. 구현해보기
  3. 중복 제거
  4. 정렬
  5. 압축된 값 부여하기
  6. 최종 코드
  7. 관련 문제 (BOJ)

'좌표 압축 기법'이란?

여러분은 배열 $A_n$을 이용해 문제를 해결하고자 한다.
그런데 배열의 수의 범위($Min(A_n)$ ~ $Max(A_n)$)가 너무 커서 주어진 제한 시간을 맞추기 힘들다.
수의 값과 무관하게 숫자 간의 대소 관계만 필요하다면, 수의 범위를 줄일 수 있을까?


$A_n$의 길이가 수의 범위보다 작다면, 좌표 압축 기법을 이용해 수의 범위를 줄일 수 있다.

어렵게 생각할 필요 없이, 숫자를 크기 순으로 정렬해 각각의 수에 0부터 숫자를 하나씩 매겨주면 된다.

 

예를 들어, $[-7, 100000, 876]$이 있다고 해보자.

크기 순으로 숫자를 매겨주면 $[0, 2, 1]$이 된다. 이렇게 수의 범위를 줄이는 테크닉을 좌표 압축이라고 한다.

 

구현해보기

좌표 압축은 아래와 같은 단계로 진행한다.

  1. 원본 배열에서 중복값을 제거한 새로운 배열을 만든다,
  2. 1에서 생성된 배열을 오름차순 정렬한다.
  3. 원본 배열의 각 원소에 대해, 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)

좌표 압축은 주로 스위핑이나 세그먼트 트리 사용시 숫자의 범위를 줄여주기 위해 사용된다.

 

상단으로

티스토리툴바