[백준 18870] 좌표 압축 (Python)
문제 링크 #
문제 해설 #
Idea #
- Sort
- 집합을 통해 압축한 unique한 좌표 목록을 정렬시키고,
정렬된 리스트 내에서 좌표와 인덱스를 딕셔너리로 맵핑
Time Complexity #
- O(N Log N) = 13,000,000
Data Size #
- N: 1 <= int <= 1,000,000
- X: -10^9 <= int <= 10^9
해설 코드 #
python
N = int(input())
X = list(map(int, input().split()))
xtoi = {x:i for i,x in enumerate(sorted(set(X)))}
print(' '.join(map(lambda x: str(xtoi[x]), X)))