문제 개요
문자열 str과 길이가 3인 부분 문자열 sub_str이 주어졌을 때, str 안에서 sub_str과 동일한 부분 수열(subsequence)이 총 몇 번 나타나는지 구하는 것이 목표입니다.
부분 수열이란 문자열에서 문자들의 상대적인 순서를 유지한 채 일부 문자를 건너뛰어 만든 시퀀스를 의미합니다. 예를 들어 "act"는 "cataract" 안에 세 번 등장합니다.
예제로 이해하기
입력 − str = "settlement", sub_str = "set"
출력 − 주어진 문자열에서 길이 3인 부분 수열의 개수: 5
설명 − 가능한 부분 수열은 다음과 같습니다.
1. set tlement,
2. se t t lement,
3. se ttlemen t,
4. s ettl e men t,
5. settlem e n t
입력 − str = "knowledge", sub_str = "now"
출력 − 주어진 문자열에서 길이 3인 부분 수열의 개수: 1
설명 − know ledge
접근 방법
이 프로그램에서 사용하는 접근 방식은 다음과 같습니다.
for 반복문을 사용해 문자열 str을 순회합니다. str[i]가 sub_str[0]과 일치하면, 그다음 문자 sub_str[1]을 현재 위치 i 이후(i < length) 범위에서 비교합니다. 인덱스 j에서 일치 지점을 찾으면, 마지막 문자 sub_str[2]를 j 이후(j < length) 범위에서 비교합니다. 두 곳 모두 일치하면 count를 1 증가시킵니다.
문자열을 str로, 부분 문자열을 sub_str로 받습니다.
함수 subset_occurrence(string str, int length, string sub_str)는 두 문자열을 받아 str에서 sub_str과 동일한 부분 수열의 개수를 반환합니다.
for 반복문으로 str을 순회합니다. i = 0부터 i < length까지 진행합니다.
str[i] == sub_str[0]이면 첫 번째 문자를 찾은 것입니다. j = i + 1부터 j < length까지 확인합니다.
str[j] == sub_str[1]이면 두 번째 문자가 일치한 것입니다. k = j + 1부터 k < length까지 확인합니다.
str[k] == sub_str[2]이면 count를 증가시킵니다.
count를 결과로 반환합니다.
예제 코드
#include<iostream>
using namespace std;
int subset_occurrence(string str, int length, string sub_str){
int count = 0;
for (int i=0; i<length; i++){
if (str[i]==sub_str[0]){
for (int j=i+1; j< length; j++){
if(str[j]==sub_str[1]){
for(int k=j+1; k<length; k++){
if(str[k]==sub_str[2])
{ count++; }
}
}
}
}
return count;
}
int main(){
string str = "TUTpoinTUTpoinTUT";
int length = str.length();
string sub_str = "TUT";
cout<<"주어진 문자열에서 길이 3인 부분 수열의 개수: "<<subset_occurrence(str, length, sub_str);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 생성됩니다 −
주어진 문자열에서 길이 3인 부분 수열의 개수: 19
시간 복잡도
이 방법은 세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³)입니다. 여기서 n은 문자열의 길이입니다. 따라서 문자열이 매우 길어지면 실행 속도가 크게 느려질 수 있으며, 이 경우 각 문자의 등장 횟수를 누적 계산하는 동적 프로그래밍 기법을 활용하면 O(n) 수준으로 최적화할 수 있습니다.