구름톤 챌린지 4주 day16 학습 일기

모자 색 예쁘다

[문제 상황]

탐색할 때 

if child in graph[parent]:

이 부분이 시간을 가장 많이 소비했고, 일부 케이스는 시간초과가 발생했다.

 

되짚어 봤을 때 graph를 2차원 배열로 선언했을 때가 문제의 원인일거라 생각했고

graph = [ [] for _ in range(N+1) ] graph의 내부를 배열 대신, set으로 바꿨다.

 

예시에서 최악의 경우를 가정했을 때, in 구문에서 시간복잡도가 대폭 증가할 것 같았다.

두가지 정도 간단하게 떠올려 봤을 때

1. graph = [ [] for _ in range(N+1) ] 로 하되, heap 또는 deque를 사용할지

2. set을 사용해서 탐색하는데 시간을 줄이기

였는데, heap을 사용하더라도 pop을 할 때 작은 순으로 정렬되어 있더라도, 결국 찾으려는 노드에서 탐색해야 하는데 시간이 걸린다.

또 deque는 pop을 하는데 시간이 단축되긴 하지만 마찬가지로 찾으려는 노드에서 탐색해야 하고, pop하는데에도 시간이 걸릴것 같아서

 

set으로 바꿨는데

정해 코드는 어떻게 풀이가 작성이 되어있을지 꼭 확인 해야겠다.

오늘의 학습 일기 끝!