[백준] 11487: 서로 다른 부분 문자열의 개수 - 파이썬[python]

1. 슬라이싱할 때마다 set 만들기

S = input()
result = 0

for i in range(1, len(S)+1): # 원소 개수
    s = set()
    j = 0
    while j+i <= len(S):
        s.add(S[j:j+i])
        j += 1
    result += len(s)

print(result)

2. 공통의 set 만들기

S = input()
s = set()

for i in range(1, len(S)+1): # 원소 개수
    j = 0
    while j+i <= len(S):
        s.add(S[j:j+i])
        j += 1

print(len(s))

생각보다 둘 사이의 메모리와 시간 차이가 크다. 특히, 메모리가 엄청나게 차이가 난다. 새로 set을 만듦으로써 메모리를 줄이고자한 게 의도한 게 아니어서 더 놀라웠다 ㅎㅎ

3. 2를 더 직관적인 i, j로 수정

S = input()
s = set()

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

print(len(s))

• 구글링하면 쉽게 볼 수 있는 코드이다.
• 나는 슬라이싱하는 개수를 i로 두고 set을 i개수만큼 앞에서부터 자르게 코드를 짰다. 예를 들어 예제는 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc의 순서로 슬라이싱되는 것이다.
• 3번 코드는 i를 슬라이싱을 시작하는 위치로 두고 거기서부터 끝까지 슬라이싱하는 개수를 하나씩 늘려간다. 예제는 a, ab, aba, abab, ababc, b, ba, bab, babc, a, ab, abc, b, bc, c의 순서로 슬라이싱 된다.

결론

내가 짠 1번 코드가 젤 좋당ㅎㅎ