정렬: 백준 18870 파이썬

문제:

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

18870번: 좌표 압축

 

정답:

import sys

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

# set 자료형으로 중복을 없애준 후 정렬
s_array = sorted(set(array))

# 딕셔너리 자료형을 사용해 시간복잡도를 크게 줄임
dic = {s_array[i]: i for i in range(len(s_array))}

for i in array:
    print(dic[i], end=' ')

 

풀이:

for문, index() 함수를 사용해서 제출했을 때는 시간 복잡도를 고려하지 못해 시간 초과가 발생했었다.

딕셔너리 자료형을 사용해 시간 복잡도를 줄여 문제를 해결할 수 있었다.

딕셔너리 자료형을 사용하면 시간복잡도를 많이 줄여주기 때문에 앞으로 딕셔너리를 고려해서 문제를 풀어야 할 필요가 있을 것 같다.

잘 숙지해두고 사용할 수 있도록 하자.