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

 

<문제>

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

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

<시간 복잡도>

이중 for 문을 사용해서 n^2의 시간 복잡도를 나타내지만, 문제를 푸는 것에는 문제가 없다고 생각했다.

시간제한 1초에 메모리 제한 512mb 이므로 약 데이터의 수가 10000000개여야 매모리 40mb이를 차지하기 때문이다.

<코드>

import sys

s = sys.stdin.readline()

a = []

for i in range(1,len(s)):
    for j in range(len(s)-i):
        a.append(s[j:j+i])
print(len(set(a)))

<해설>

완전 탐색 비슷하게 풀었는데 핵심이라고 하면 for 문의 사용법이다. 

밖의 for문은 1~문자열의 길이까지 하고 만들어진 문자열을 리스트에 포함한다.

다음으로 set을 이용해서 중복된 것을 제거하는 방식으로 답을 결정한다.