[Python]18870번, 좌표 압축, 딕셔너리, enumerate() 함수

문제

 

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

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

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

 

입력

 

첫째 줄에 N이 주어진다.

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

 

출력

 

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

 

풀이

 

간단하게 리스트와 정렬, 문자열과 replace() 함수를 사용해 문제를 풀면 아무리 해도 시간초과가 난다.

 

이는 리스트 순회나 replace() 함수의 성능이 굉장히 떨어지기 때문인데,

 

덕분에 별 거 아닌 문제라고 생각했다가 예상치 못하게 시간을 쓰게 되었다.

 

그렇게 약 한 시간 이리저리 돌리면서 풀어보다 발견한 것이 enumerate() 함수.

 

이 아이는 진짜 특이하게도 리스트나 튜플을 매개변수로 받아 각 요소의 (인덱스, 값) 을 쌍으로 반환한다.

 

덕분에 인덱스와 값을 키-값으로 하는 딕셔너리를 단 한 줄로 생성할 수 있다는 장점이 있다.

 

물론 그 순서를 뒤집어 리스트의 값을 키로, 인덱스를 값으로 생성할 수도 있다.

 

이렇게 하면 매번 리스트를 순회하거나 replace()를 사용할 필요 없이 바로 답을 출력할 수 있게 된다.

 

풀이 과정은 다음과 같다.

 

1. 주어진 리스트에서 중복을 제거(set 사용)한 뒤 정렬한다(sorted() 사용).
2. 정렬된 리스트의 값-인덱스를 키-값으로 하는 딕셔너리를 생성한다(enumerate() 사용).
3. 맨 처음 받았던 리스트를 순회하며, 딕셔너리에서 주어진 리스트의 값을 인덱스로 가진 딕셔너리 값을 출력한다.

코드는 아래와 같다.

import sys

n = int(sys.stdin.readline())

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

b = sorted(set(a))

c = {x: i for i, x in enumerate(b)}

for i in a:
    print(c[i], end=' ')

print(c)