[백준/Python] 좌표 압축

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

[처음 코드]

n = int(input())
nums = list(map(int, input().split()))

comp = sorted(list(set(nums)))

for num in nums:
	print(comp.index(num), end = ' ')

 

처음엔 index() 를 사용해서 리스트에서의 인덱스를 찾아 출력하도록 하였다. 그랬더니 시간 초과가 났다. 질문하기에서 찾아보니 index() 는 리스트를 순차 탐색하므로 한 번 사용할 때 O(N) 만큼 걸려서 결국 O(N^2) 만큼 걸려서 시간 초과가 난 것이었다. 시간 초과가 나지 않게 하기 위해서는 딕셔너리를 사용해야 했고 딕셔너리는 한 번에 O(1) 만큼 걸려서 결국 O(N) 만큼 걸리게 된다.

 

[최종 코드]

n = int(input()) # 숫자의 개수
nums = list(map(int, input().split())) # 숫자 리스트

comp = sorted(list(set(nums))) # 중복 제거한 후 정렬
dic_comp = {comp[i] : i for i in range(len(comp))} # 딕셔너리로 변경

for num in nums:
	print(dic_comp[num], end = ' ') # 딕셔너리에서 인덱스 값을 찾아 출력