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

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

 

아이디어

• 입력된 리스트를 정렬한 형태의 리스트를 하나 더 선언
• enumerate() 함수로 인덱스와 값을 매칭시킨 딕셔너리 생성
• 이러면 값의 크기순으로 순서가 매겨짐
• 이를 기존 리스트의 값들을 순서대로 딕셔너리의 값을 불러오기

구현

N = int(input())
li = list(map(int, input().split()))

result = [0 for i in range(N)]
tmp = sorted(set(li))

rank = {num: i for i, num in enumerate(tmp)}

print(*(rank[num] for num in li))

 

마무리

처음엔 enumerate()함수가 떠오르지 않아 반복문을 통해 구현했었다.

하지만 N의 크기가 백만까지의 범위를 가지고 있어 이럼 시간복잡도가 너무 높아져 시간초과가 발생했다.

딕셔너리를 중간에 생각해 내는게 익숙하지 않아서 그런듯 하다 딕셔너리의 존재도 항상 인지하고 있자.