문자열 str이 주어졌을 때, 시작 문자가 X와 같고 끝 문자가 Y와 같은 부분 문자열의 개수를 구하는 것이 목표입니다. 예를 들어 입력이 "artact"이고 X='a', Y='t'라면 해당하는 부분 문자열은 "art", "act", "artact"로 총 3개입니다.
예시로 이해하기
입력 − str="abcccdef", X='a', Y='c'
출력 − 문자 X로 시작하고 문자 Y로 끝나는 부분 문자열의 개수: 3
설명 − 해당하는 부분 문자열은 다음과 같습니다.
"abc", "abcc", "abccc" → 총 3개
입력 − str="tempest", X='t', Y='t'
출력 − 문자 X로 시작하고 문자 Y로 끝나는 부분 문자열의 개수: 3
설명 − 해당하는 부분 문자열은 다음과 같습니다.
"t", "tempest", "t" → 총 3개
적용된 접근 방식
이 문제는 문자열을 단 한 번만 순회하면서 해결할 수 있습니다. 문자열을 탐색하다가 문자 X를 만나면 X의 누적 개수를 1 증가시키고, 문자 Y를 만나면 지금까지 세어 온 X의 개수를 결과값에 더합니다. 핵심 아이디어는 각 Y 위치마다 "그 앞에 등장한 모든 X"와 짝을 이루는 부분 문자열이 새로 만들어진다는 점입니다.
- 문자열 str을 받고, 길이를 str.size()로 계산합니다.
- 함수 X_Y(string str, int length, char X, char Y)는 문자열 str과 문자 X, Y를 매개변수로 받아 X로 시작하고 Y로 끝나는 부분 문자열의 개수를 반환합니다.
- 결과를 저장할 count를 0으로 초기화합니다.
- x_total은 str에서 지금까지 발견한 문자 X의 개수를 나타냅니다.
- for 루프를 사용해 i=0부터 i<length까지 str을 순회합니다.
- str[i]==X이면 x_total++로 X의 개수를 증가시킵니다.
- str[i]==Y이면 count에 x_total을 더합니다. 앞서 X가 없었다면 x_total은 0이므로 결과에 영향을 주지 않고, X가 있었다면 해당 Y는 X로 시작하는 부분 문자열의 끝 문자가 됩니다.
- 모든 순회가 끝나면 count를 최종 결과로 반환합니다.
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 배열 없이 상수 공간(O(1))만 사용하기 때문에 매우 효율적입니다.
예제
#include <bits/stdc++.h>
using namespace std;
int X_Y(string str, int length, char X, char Y){
int count = 0;
int x_total = 0;
for (int i = 0; i < length; i++){
if(str[i] == X){
x_total++;
}
if (str[i] == Y){
count = count + x_total;
}
}
return count;
}
int main(){
string str = "defaabbcchhkl";
int length = str.size();
char X = 'd';
char Y = 'a';
cout<<"Count of substrings that starts with character X and ends with character Y are: "<<X_Y(str, length, X, Y);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of substrings that starts with character X and ends with character Y are: 2