시간복잡도와 함께 올라가는 내 정신복잡도

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

 

이러한 문제가 있다. 좌표압축 어쩌고인데

대충 구하는 로직은 어렵지 않았지만 입력값이 100만개에 육박하기때문에 시간복잡도를 줄이는 것이 관건이었다.

 

나의 스무스한 흐름대로 적어본 최초의 코드는 이러하다.

 

n = int(input())
coordinates = list(map(int, input().split()))

set_coord = sorted(set(coordinates))

answer = []
for i in coordinates:
    answer.append(set_coord.index(i))

print(*answer)

 

대충 입력을 받고, set으로 좌표들을 저장하고 정렬하여 

입력받은 coordinate의 값들의 인덱스 값을 알아내면 정답을 알 수 있었다. 

캬 짧고 좋다~ 했는데 역시나 시간초과가 떠버렸다.

 

정확히 알아보자면, 문제에서 원하는 출력값이 한줄로 되어있었기에 그것을 맞추려고

다른 answer 리스트를 만들어서 저장하고, 출력하려하였다.  

 

for i in coordinates:
    answer.append(set_coord.index(i))

 

이 부분은 내가 가진 모든 coordinates 값들에 대해 set_coord.index(i)를 호출하게 되므로, 최악의 경우 n^2의 복잡도가 된다. 100만개를 돌리기엔 시간이 턱없이 부족할 것이었다.

 

찾아보니 딕셔너리 어쩌고 하길래, 딕셔너리를 이용하여 수정을 해보았다.

혹시나 하여 입력도 sys 표준 입력으로 바꾸었다.

 

import sys
n = int(input())
coordinates = list(map(int, sys.stdin.readline().split()))

set_coord = sorted(set(coordinates))

coord_index_dict = {}
for i in set_coord:
    coord_index_dict[i] = set_coord.index(i)

indices = [str(coord_index_dict[i]) for i in coordinates]


print(*indices)

 

어디가 바뀌었는가??

 

coord_index_dict = {}
for i in set_coord:
    coord_index_dict[i] = set_coord.index(i)

 

그래. 하라는대로 딕셔너리 자체에 인덱스를 저장해본 것이다. 어찌되었든 set에 집어넣고 정렬한 좌표 값의 인덱스가 곧 답이었기때문에 인덱스를 찾아내면 되니까..

 

딕셔너리가 무슨 역할을 한다고 시간을 줄일 수 있나 했더니.. 저 방법도 틀렸다!!

 

문제는 딕셔너리의 사용이 아니라 .index() 메서드의 사용이었다.

 

index() 는 결국 해당 리스트를 전부 순회하여 인덱스에 맞는 값을 찾는다. 이러한 접근법은 여전히 n^2의 복잡도를 가졌다. 그럼 딕셔너리를 어떻게 쓰는데???????????????? 어?????????

 

coord_index_dict = {}
for index, value in enumerate(set_coord):
    coord_index_dict[value] = index

 

정답은 enumerate와 함께 사용하는 것이다. 

 

특정 값의 인덱스를 검색하지 않고, 바로 enumerate를 사용해 인덱스와 value를 저장해주었다.

 

그러니.. 어찌저찌 통과했다.

 

enumerate() 를 많이 쓰지 않았는데, 종종 등장하는 것을 보고 그저 넘어갔다. 

오늘 2 문제정도 사용해보았는데, 나름 유용한것 같으니 잘 기억해두자.

 

망할 시간복잡도