백준 18870: 좌표 압축 (Python)

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

18870번: 좌표 압축

 

import sys

n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
num_set = sorted(list(set(num)))

for i in num:
    print(num_set.index(i), end=' ')

 

숫자를 num으로 입력받아 리스트로 만들고

중복을 제거하고 정렬한 리스트를 하나 더 만들어서 그 리스트의 인덱스를 출력하도록 했다

근데 시간 초과가 떴다.... 인덱스를 하나하나 찾는데 시간이 오래 걸려서 그렇다고 한다

** 리스트.index(i) : 시간 복잡도 O(n) **

 

import sys

n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
num_set = sorted(list(set(num)))
num_dic = {num_set[i] : i for i in range(len(num_set))}

for i in num:
    print(num_dic[i], end=' ')

 

그래서 딕셔너리를 이용했다

딕셔너리는 {key:value}로 값을 저장하는데 key는 중복 허용 X

딕셔너리에 key값을 num, value값을 더 작은 숫자의 개수로 넣어주고 num을 돌면서(key - num) 값을 출력했다!

** 딕셔너리 : 시간 복잡도 O(1) **