백준 - 서로 다른 부분 문자열의 개수(11478)

유재우·2022년 7월 2일
0

문제

문자열 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의 서로 다른 부분 문자열의 개수를 출력한다.
  • 예제 입력 1
ababc
  • 예제 출력 1
12

  • 내가 생각한 풀이
word = input()
s = set()
for i in range(len(word)):
    s.add(word[i])
    s.add(word[i:i+1])
print(len(s))
  • 우선 문자열을 받아와 저장하고 그 크기 만큼 for문을 돌려 s 집합에 문자열의 슬라이싱을 추가하여 중복 된 값을 제거하고 그 집합의 크기를 출력하려는 방식으로 접근하였으나 슬라이싱을 집합에 추가하는 과정에서 문자열의 크기가 커질수록 시간도 오래걸리고 코드를 어떤식으로 작성해야 할지 모르겠다.

  • 정답
import sys
input = sys.stdin.readline
S = input().strip()
subset = set()
for size in range(1, len(S)+1):
    for i in range(len(S)-size+1):
        j = i+size
        subset.add(S[i:j])
print(len(subset))

  • 전 부터 느끼는 거지만 항상 해결방안를 생각해내는 것 자체까지는 잘 하지만 그걸 구현하려할 때에 이중for문을 항상 배제하고 생각 하는 것 같다.
profile
끝없이 탐구하는 iOS 개발자 유재우입니다!

0개의 댓글