[백준 18870번] 좌표 압축 - 파이썬

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

18870번: 좌표 압축

 

💡문제 분석 요약

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

💡알고리즘 설계

1. 좌표의 수를 입력받는다.

2. 좌표를 list 형태로 입력받는다.

3. list형태의 좌표를 set으로 바꾸어 중복을 제거하고, 오름차순으로 정렬한다.

4. hash에 key는 중복이 제거되고 오름차순으로 정렬된 좌표(setX[i]), value는 좌표의 순위(0부터 set의 길이만큼)를 저장한다.

5. hash[좌표]를 출력한다.

 

💡코드

import sys
input = sys.stdin.readline

N=int(input())
X=list(map(int, input().split()))
setX=sorted(set(X))

hash={setX[i] : i for i in range(len(setX))}

for i in X:
    print(hash[i], end=' ')

💡시간복잡도

좌표 입력, 집합 변환, 해시 저장, 출력 모두 O(n)

 

💡 느낀점 or 기억할 정보

짧지만 리스트와 집합, 해시를 모두 사용해야해서 어려웠다.