[백준] 11478 서로 다른 부분 문자열의 개수 (실버3) / list, set, dict 시간복잡도 비교

문제요약

나의 코드 및 설명 01 - list(시간초과)

• 리스트로 풀려고 했다가 시간초과가 발생했다.

s = list(input())

length = len(s)

v = []

for l in range(1,length+1):
    for i in range(length-l+1):
        check = "".join(map(str, s[i:i+l]))
        if check not in v:
            v.append(check)

print(len(v))

나의 코드 및 설명 02 - set

• set을 써서 문제를 해결할 수 있었다. set의 추가 연산은 <add>이다.

s = input()
result = set()

for l in range(len(s)):
    for i in range(len(s)-l+1):
        temp = s[i:i+l]
        result.add(temp)

print(len(result))

list 주요 연산 시간복잡도

set 주요 연산 시간복잡도

dict 주요 연산 시간복잡도

피드백

set을 사용하여 문제를 해결할 수 있었다. list, set, dict 의 주요 연산 시간복잡도 표는 벌써 세 번째 포스팅하는데, 꼭 암기할 필요가 있다. set에서 len(S)의 연산은 시간 복잡도가 O(1)이다.