[백준 11478] 서로 다른 부분 문자열의 개수 - Python (해시맵)

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

 

 

1번째 풀이 - O(N^2)

import sys

input = sys.stdin.readline

S = input().rstrip()

for i in range(len(S)):
    if S[i] in result:
        result[S[i]] += 1
    else:
        result[S[i]] = 1

    if i == len(S) - 1:
        break

    current_string = S[i]

    for j in range(i + 1, len(S)):
        current_string = current_string + S[j]
        if current_string in result:
            result[current_string] += 1
        else:
            result[current_string] = 1

print(len(result))

 

시간복잡도 O(n^2)이 걸리는 풀이로 작성했다. 해당 코드를 python의 set 자료형을 활용하면 간단하게 작성할 수 있다. 

 

---

python set() 활용 풀이 - O(N^2)

import sys

input = sys.stdin.readline

S = input().rstrip()

result = set()

for i in range(len(S)):
    for j in range(i + 1, len(S) + 1):
        result.add(S[i:j])
print(len(result))

 

set(집합) 자료형은 집합의 중복을 제거하고 순서를 보장하지 않는 리터럴 객체를 생성한다.