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

---

풀이

풀이 확인하기

이번 문제는 set을 사용하면 쉽게 풀 수 있다. set 자료형은 중복되는 값은 자동으로 들어가지 않는데, 이를 이용해 “aaa”와 같이 겹치는 요소들을 쉽게 제거할 수 있다. 이중 반복문을 통해 가능한 경우의 수의 부분 문자열들을 전부 set에 넣고, set의 요소들의 개수만 출력하면 되는 것이다.

(set 자료구조는 O(1)의 시간복잡도를 가지는 매우 빠른 자료구조인데, 이 원리에 대하여 궁금하다면 hash table을 검색해보자. 참고로 파이썬의 다른 자료구조인 dictonray 역시 비슷한 구조를 가지고 있다.)

import sys
input = sys.stdin.readline

line = input().strip()

num = set([])

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

print(len(num))

• baekjoon
• python