[Python Silver II 18870] 좌표 압축

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

18870번: 좌표 압축

 

시간 제한	메모리 제한
2초	512MB

 

문제

• 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
• X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
• Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

 

입력

• 첫째 줄에 N이 주어진다.
• 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

출력

• 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

알고리즘 분류

• 정렬
• 값 / 좌표 압축

 

---

 📖 Code

from collections import deque

N = int(input())
result = {}
count = 0
lst = list(map(int, input().split()))
lst_set = set(lst)
set_lst = deque(sorted(list(lst_set)))
for _ in range(len(set_lst)):
    min_num = set_lst.popleft()
    result[min_num]= count
    count+=1
for i in lst:
    print(result[i], end=" ")

 ✅ Comment

 

시간 복잡도 떄문에 까다로웠었는데.



파이썬 딕셔너리를 사용하면 쉽게 해결할 수 있었다.