이 문제에서는 문자열 str이 주어지며, 해당 문자열에 포함된 모든 고유한(distinct) 부분 문자열의 개수를 구해야 합니다. 부분 문자열(substring)이란 기존 문자열의 연속된 일부분으로, 그 길이는 원본 문자열보다 작거나 같을 수 있습니다.
예시를 통해 문제와 해결 방법을 자세히 살펴보겠습니다.
문제 예시
입력 − str = "wxyz"
출력 − 고유한 부분 문자열의 개수: 10
설명 − 다음과 같은 고유한 부분 문자열들이 존재합니다.
wxyz, wxy, wx, w, xyz, xy, x, yz, y, z → 총 10개
입력 − str = "zzzz"
출력 − 고유한 부분 문자열의 개수: 4
설명 − 중복을 제외하면 다음 4개만 남습니다.
zzzz, zzz, zz, z
해결 접근 방식
문자열 str을 입력으로 받습니다.
중복 제거를 위해 비어 있는
unordered_set<string>타입의 집합 "myset"을 선언합니다.바깥쪽 반복문: i를 0부터 문자열 크기보다 작을 때까지 1씩 증가시키며 순회합니다.
매번 새로운 빈 문자열 space("")를 선언합니다.
안쪽 반복문: j를 i부터 문자열 크기보다 작을 때까지 1씩 증가시키며 순회합니다.
각 단계마다 space에 str[j]를 이어 붙여 부분 문자열을 만듭니다.
완성된 space를 myset에 삽입합니다. set은 중복을 자동으로 제거하므로 고유한 부분 문자열만 저장됩니다.
최종적으로 myset의 크기를 출력합니다. 이것이 곧 고유한 부분 문자열의 개수입니다.
예제 코드
#include<iostream>
#include<unordered_set>
using namespace std;
int main(){
string str = "aaaa";
unordered_set<string> myset;
int i, j;
for (i = 0; i < str.size(); ++i){
string space = "";
for (j = i; j < str.size(); ++j){
space = space + str[j];
myset.insert(space);
}
}
cout << "count of distinct substring is: " << myset.size();
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
count of distinct substring is: 4
동작 원리 정리
이 알고리즘은 가능한 모든 시작 위치(i)와 끝 위치(j)의 조합을 이중 반복문으로 탐색하며 부분 문자열을 생성합니다. 생성된 부분 문자열은 unordered_set에 삽입되는데, set은 해시 기반으로 동작하여 중복 요소를 자동으로 걸러줍니다. 따라서 최종적으로 set에 남아 있는 원소의 개수가 바로 고유한 부분 문자열의 총개수가 됩니다.
시간 복잡도는 O(n²)개의 부분 문자열을 생성하고 각각의 저장 및 비교 비용이 추가되므로, 최악의 경우 O(n³)에 가까울 수 있습니다. 하지만 구현이 간단하고 직관적이어서 문자열 길이가 짧은 경우에는 매우 실용적인 방법입니다.