[백준] #11478 서로 다른 부분 문자열의 개수 python

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

11478번: 서로 다른 부분 문자열의 개수

📕 설명 📕

itertools의 combinations를 사용하여 해결하였다.

 

이 경우, 여러 부분집합들이 연속된 string 에 포함되어야 하는데, 순서가 중요해진다.

 

이를 고려하여, str에 저장하여 풀이하였더니, 메모리 초과가 떴다.

 

그래서 join함수를 이용하여 다음과 같이 풀이하였더니 시간 초과가 발생하였다.

from itertools import combinations
S = input()
result = 0
for i in range(len(s)):
    for j in range(i,len(s)):
        total.add(s[i:j+1])#i번째 문자부터 부분문자열 구하기

for i in range(1, len(S)+1):
    for j in set(combinations(S,i)):
        if len(j) == 1:
            result += 1
            continue
        check = True
        j = ''.join(j)
        if j not in S:
            check = False
        if check:
            result += 1
print(result)

이를 해결한 코드는 아래와 같다.

🧑🏻‍💻 나의 풀이 🧑🏻‍💻

S = input()
result = set()
for i in range(len(S)):
    for subset in range(i, len(S)):
        result.add(S[i:subset+1])
print(len(result))