[python][백준/BOJ] 18870번 : 좌표 압축

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

18870번: 좌표 압축

 

✅ 첫 번째 시도 

import sys

n=int(sys.stdin.readline())
x=list(map(int,sys.stdin.readline().split()))

#python 얕은 복사(shallow copy)
#dx=x[:] 로도 가능
dx=set(x.copy())
dx=list(dx)
dx.sort()
for i in x:
    print(dx.index(i),end=' ')

❗ .index() 를 통해 매번 호출하는 것은 O(N)의 시간복잡도를 가지기 때문에 오래 걸린다. 

❗ 다른 방법을 생각해본다. => 딕셔너리를 활용해보는 것을 떠올림!

 

✅ 최종 코드

• 인덱스의 값을 딕셔너리로 저장함 (key: x리스트의 값, value : x리스트 값의 인덱스)
• 그 후 반복문을 돌면서 키에 해당하는 인덱스의 값을 출력한다.

import sys

n=int(sys.stdin.readline())
x=list(map(int,sys.stdin.readline().split()))

#python 얕은 복사(shallow copy)
#dx=x[:] 로도 가능
dx=set(x.copy())
dx=list(dx)
dx.sort()

nd=dict()
for i in range(len(dx)):
    nd[dx[i]]=i

for i in x:
    print(nd[i],end=' ')