종우의 삶 (전체 공개)
시간복잡도와 함께 올라가는 내 정신복잡도 본문
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 문제정도 사용해보았는데, 나름 유용한것 같으니 잘 기억해두자.
망할 시간복잡도
'일지 > 코딩 테스트 , Algorithm' 카테고리의 다른 글
그래프 탐색? 그게 어떻게 하는 건데 (1) | 2024.06.10 |
---|---|
2분 안에 알아보는 이진 탐색 (Binary Search) (1) | 2024.06.08 |
힙하지 않은 힙 (0) | 2024.06.06 |
큐는 어렵다. 큐는 모르겠다. 큐큐큐;;; (0) | 2024.06.05 |
행렬과 행렬과 배열과 행렬과 배렬과 행열과...... (0) | 2024.06.03 |