[코테, 알고리즘] 백준 class 3 - 좌표 압축

[18870] 좌표 압축

그냥 지나가려고 했는데 생각보다 뭔가 있는 알고리즘 같아서 (??) 정리해보려고 한다.

좌표 압축이란?

• 모든 구간이 아니라, 중요한 구간(숫자)만 들고 있는 기법
• ⭐값보다 값의 순위가 더 중요할 때⭐ 사용한다.
• 값을 다루기 편한 임의의 값으로 변경하되 순위는 유지하여 문제를 풀 수 있도록 만든다.
• 입력값의 범위가 매우 클때, 수의 값에 상관없이 좌표들 사이의 대소관계만 알면 될때 (순위만 알면 될때) 좌표 압축을 사용하면 수의 범위를 줄일 수 있다.
• ex) x,y의 범위가 0 ~ 2^31-1 이고, 좌표 5000개를 입력받는다고 했을때, 입력 좌표를 그대로 반영하여 푼다면 배열의 크기가 2^31-1이 되어야 하지만, 좌표 압축을 한다면 배열은 5000만으로도 충분하다.

동작 과정

1. 좌표 압축을 할 배열을 임시의 배열에 옮겨 중복이 없고 정렬된 상태로 만든다.
2. 좌표 압축을 할 배열의 각 수들이 임시의 배열에서 몇번째 인덱스에 해당하는 수인지 찾는다.

코드

• 첫번째 코드 (시간초과)

N = int(input())
X = list(map(int, input().split()))
sortedX = sorted(list(set(X)))
answer = " ".join([str(sortedX.index(x)) for x in X])
print(answer.strip())

• 두번째 코드 (정답)

N = int(input())
X = list(map(int, input().split()))
sortedX = sorted(list(set(X)))
sortedX_dict = dict()

for i, x in enumerate(sortedX):
  sortedX_dict[x] = i

answer = " ".join([str(sortedX_dict[x]) for x in X])
print(answer.strip())

중복제거, 정렬 후에 index() 메소드로 인덱싱을 하려고 했더니 시간초과가 나서 인덱스를 딕셔너리로 저장해 사용해서 시간을 줄였다.