[Python] 11478번 서로 다른 부분 문자열의 개수

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

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

---

 

22/11/30

 

 

단계별로 풀어보기에서 풀은 문제로, 부분 문자열을 찾아내는 방법과 집합 자료구조에 대한 사용법만 알고 있다면 쉽게 풀 수 있는 문제이다.

---

 

문제 접근 방식:

 

 

모든 부분 문자열을 찾아내고, 이를 부분 문자열 집합에 넣어서 그 집합의 크기를 구하면 끝나는 문제이다.

 

부분 문자열을 찾아내는 방법은, 문자열 슬라이싱을 이용하여 찾아낼 수 있다.

 

부분 문자열의 길이가 될 수 있는 $len \ sub \ string$을 $1$부터 $len(S)$까지 for문으로 돌리고, 그 for문 안에 부분 문자열이 시작하는 위치인 $i$를 이용해 for문으로 구현, 즉, 이중 for문으로 구현함으로써 시간 복잡도 $O(n^2)$으로 모든 부분 문자열을 탐색할 수 있다.

 

이 부분 문자열들을 집합에 넣으면 끝이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11478번 서로 다른 부분 문자열의 개수
# 자료 구조, 문자열, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵
'''
접근 방법:
문자열 인덱싱 + 집합
'''
S = input()
sub_string_set = set()
for len_sub_string in range(1, len(S)+1):
    for i in range(len(S)-len_sub_string+1):
        sub_string = S[i:i+len_sub_string]
        sub_string_set.add(sub_string)

print(len(sub_string_set))