[Hash] Dictionary 시간복잡도 (2) - 시간초과 예시

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

위 문제가 Hash 자료구조를 사용하지 않고 구현하면 시간초과가 나오기 쉬운 대표적인 문제라고 생각한다.

 

내가 처음 작성한 코드이다.

#time complexity: O(N) + O(N*(N-1)) = O(N^2) = 4억인뎀....
import sys
input = sys.stdin.readline
N = int(input())
words = {input().strip(): i for i in range(N)}
# print(words)

S_len = 0
S, T = "", ""

found = False
for nS in words.keys():
    nS_len = len(nS)
    if found is True and nS_len <= S_len:
        continue
    for nT in words.keys():
        if nS in nT[:nS_len] and nS is not nT:
            if nS_len > S_len:
                S, T, S_len = nS, nT, nS_len
                break
print(f"{S}\n{T}") if words[S]<words[T] else print(f"{T}\n{S}")

Big-O time complexity가 O(N^2) = 400,000,000 이라는 계산은 하였다만, 

dictionary내에서 특정 String을 prefix로 가지고 있는 단어 찾는 방법이 딱히 떠오르지 않아서... '평균 시간 복잡도 안에 계산되서 문제없을수도?'라는 안일한 생각과 작성한 코드

 

왜 O(N^2)인가?

input List를 Dictionary에 넣을 때 O(N) +

이중 for문 : nS에 대한 for문 O(N) *

                   nT search하는 for문 O(N)

 

= O(N + N^2) = O(N^2)

 

즉 element의 빠른 탐색을 위해 dictionary structure를 이용하자!! 는 생각은 했지만,

( list(Array)는 한 element 찾는데에 iteration이 필수적이라 O(len(list)) 이지만, dictionary(Hashmap)는  O(1)이나까! )

결국 그 쓰임을 사용하지 못한 case...