접두사

1141번: 접두사

 

나의 코드

import sys

def _head_test(str_dict, n):
    not_use = set()
    for i in str_dict:
        now_str = ''
        for j in i:
            now_str += j
            if (now_str in str_dict) and (now_str != i):
                not_use.add(now_str)
    return n - len(not_use)

n = int(sys.stdin.readline())
str_dict = {}
for _ in range(n):
    str_dict_key = sys.stdin.readline().rstrip()
    if str_dict_key in str_dict:
        n -= 1
    else:
        str_dict[str_dict_key] = 0
print(_head_test(str_dict, n))

 

시간 복잡도

for i in str_dict : 딕셔너리 키 값을 순회 ( 선형 시간 복잡도 )
    now_str = ''
    for j in i : 단어를 순회 ( 선형 시간 복잡도 )
        now_str += j
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도( O(n**2) )