What I Learned/Algorithm Practice

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

Interrobang 2022. 10. 3. 17:23

<문제 링크>

 

 

18870번: 좌표 압축

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

www.acmicpc.net

 

<문제 풀이>

import sys
N = int(input())

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

coord_list_sorted = sorted(list(set(coord_list)))

coord_dict = {}
for i in range(len(coord_list_sorted)):
    coord_dict[coord_list_sorted[i]] = i

for i in coord_list:
    print(coord_dict[i], end=' ')

18870 입출력 예시

*key point: set() 함수를 이용한 중복 제거 후 sorted() 함수를 통해 정렬하면 해당 요소의 index가 원하는 값( Xi > Xj를 만족하는 서로 다른 좌표의 개수)을 나타내게 된다. 시간 초과를 해결하기 위해서 dictionary 자료형을 활용한다.