🟩 [백준] [Python] [Class3] 18870번_좌표 압축

문제

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

18870번: 좌표 압축

풀이

# 백준 18870번 문제 - 좌표 압축
n = int(input())
x = list(map(int, input().split()))
new_x = list(sorted(set(x)))

dict = {new_x[i]: i for i in range(len(new_x))}

for i in x:
    print(dict[i], end=" ")

맨 처음 시간초과가 떠서 시간복잡도를 생각하였다. 

N이라는 숫자가 100만이기 때문에 시간복잡도를 먼저 생각했어야 했는데 하지 못했다. 

index(i)는 시간복잡도가 O(n)이고 딕셔너리는 O(1) 이므로 딕셔너리를 사용해야 했다.