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

안녕하세요. 성조입니다.

이 포스팅은 Python 3 버전을 기준으로 풀이됐습니다.

 

몇 차례 풀이했지만 결국 개선된 코드가 가장 빠른 응답을 가진 문제였습니다

 

 

문제 출처

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의 서로 다른 부분 문자열의 개수를 출력한다.

 

코드

import sys

S = sys.stdin.readline().rstrip()

cnt = set()

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

print(len(cnt))

S 문자열에 공백을 모두 제거하는 strip()를 활용해도 된다.

 S = sys.stdin.readline().strip()

 

개선 코드

S = input()

cnt = set()

data_length = len(S)

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

print(len(cnt))

 

풀이

1. 첫 번째 반복문에서 S문 자열의 길이만큼 반복 입력을 받는다. 즉, i의 문자열 인덱스 이다.

2. j는 S의 문자열 인덱스이다.

3. cnt.add는 set 자료형으로 선언한 cnt 변수에 부분 문자열을 추가하는 코드를 의미한다.

3-1. S [i:j+1]은 S의 i번째 문자부터 j번째 문자까지 부분 문자열을 의미한다. j+1인 이유는 인덱싱은 -1 값이므로 i ~ j까지 범위를 반복하기 위해서는 +1을 해줘야 한다.

3-2. [예시] S="abc" 이면서,  i=0, j=2일 때는 S [0:2] = "ab" 값이 cnt 변수에 문자열로 하나 추가된다. 이 연산이 반복되면서 a부터 ababc까지 모두 반복한다.

4. 연산된 cnt의 딕셔너리 값의 길이를 출력하면 a, b, a, b, c, ab, ba, ab... 회문 형식의 문자열 값들이 몇 개인지 측정할 수 있게 된다.

 

---

오타나 이해가 안 가는 부분이 있다면 언제든지 댓글로 얘기해 주시면 감사드리겠습니다.

언제든지 효율적으로 구현할 수 있는 피드백 방향을 제시해 주시면 참고하고, 학습하여 코드 개선할 수 있도록 노력해 보겠습니다.

다음 포스팅 때 뵙겠습니다!