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

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

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

문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

출력

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

---

풀이

이번에도 역시 딕셔너리(해시)를 통해 풀었다!

처음에는 부분 문자열을 나열하는 것에 대한 고민을 했다.

'연속된'이라는 키워드가 있어서 어렵지 않게 부분 문자열의 리스트를 만들 수 있었다.

 

abcde라면

i가 첫 문자를, j가 뒤에 붙을 문자를 탐색하여 추가하는데

a, ab, abc, abcd, abcde, b, bc, bcd, bcde, c, cd, cde, d, de, e 이런 식으로 추가가 된다

a, b, c, d, e, ab, ... 이렇게 생각하는 것 보다 쉽게 짤 수 있었다.

 

처음 코드는 마지막에 set으로 중복을 제거해줬다

처음부터 set으로 받는게 더 효율 적일 것 같다고 생각했는데

처음부터 set으로 받아보니 큰 차이가 없었다

python코드

# 리스트로 받은 후 변환
S = input()
s_arr = []

for i in range(len(S)):
    text = ''
    for j in range(i,len(S)):
        text += S[j]
        s_arr.append(text)
set_arr = set(s_arr)
print(len(set_arr))

# set으로 바로 받기
S = input()
s_arr = set()

for i in range(len(S)):
    text = ''
    for j in range(i,len(S)):
        text += S[j]
        s_arr.add(text)
print(len(s_arr))