문제 소개
문자열 str[]이 주어지며, 이 문자열은 'a', 'b', 'c' 세 문자만으로 구성되어 있습니다. 우리의 목표는 이 세 문자가 모두 포함되지 않은 부분 문자열(substring)의 개수를 구하는 것입니다. 예를 들어 어떤 문자열에 대해 "a", "b", "c", "abb", "bba", "bc", "ca", "ccc"와 같은 부분 문자열은 유효하지만, 'a', 'b', 'c' 세 문자가 모두 들어 있는 "abc", "bcca", "cab" 같은 부분 문자열은 제외됩니다.
예제를 통해 자세히 살펴보겠습니다.
입력 − str[] = "aabc"
출력 − {'a', 'b', 'c'} 세 문자를 동시에 포함하지 않는 부분 문자열의 개수: 8
설명 − 해당하는 부분 문자열은 다음과 같습니다: "a", "a", "b", "c", "aa", "ab", "bc", "aab"
입력 − str[] = "abcabc"
출력 − {'a', 'b', 'c'} 세 문자를 동시에 포함하지 않는 부분 문자열의 개수: 11
설명 − 해당하는 부분 문자열은 다음과 같습니다: "a", "b", "c", "a", "b", "c", "ab", "bc", "ca", "ab", "bc"
해결 접근 방식
이 접근 방식의 핵심 아이디어는 길이가 n인 문자열의 전체 부분 문자열 개수가 n*(n+1)/2라는 사실을 활용하는 것입니다.
문자열을 순회하면서 각 문자('a', 'b', 'c')를 만날 때마다 나머지 두 문자(('b','c'), ('c','a'), ('a','b'))의 마지막 등장 인덱스를 확인합니다. 그런 다음 두 인덱스 중 최솟값을 count에서 빼줍니다. 현재 문자를 부분 문자열에 포함시키려면 다른 문자 하나를 걸러내야 하고, 그래야 세 문자가 모두 포함되는 경우를 피할 수 있기 때문입니다.
문자열 str을 문자 배열로 받습니다.
함수 sub_without_all(char str[], int size)는 문자열과 그 길이를 매개변수로 받아 'a', 'b', 'c'가 모두 포함되지 않은 부분 문자열의 개수를 반환합니다.
str[]의 모든 가능한 부분 문자열 개수인 size*(size+1)/2를 초기 count 값으로 설정합니다.
'a', 'b', 'c'의 마지막 인덱스를 저장할 변수 a, b, c를 선언하고 모두 0으로 초기화합니다.
for 루프를 사용하여 i=0부터 i<size까지 str[]을 순회합니다.
str[i]=='a'라면 'a'의 인덱스를 a=i+1로 갱신하고, 'b'와 'c'의 인덱스 중 최솟값을 count에서 뺍니다. 이렇게 하면 현재 'a'를 포함하는 부분 문자열이 다른 문자를 포함하더라도 세 문자가 모두 들어가지 않게 됩니다.
str[i]=='b' 또는 str[i]=='c'인 경우에도 앞 단계와 동일한 방식으로 처리합니다.
순회가 끝나면 count에는 세 문자가 모두 포함되지 않은 부분 문자열의 개수가 저장됩니다.
count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int sub_without_all(char str[], int size){
int update_size = size * (size + 1);
int count = update_size / 2;
int a, b, c;
a = b = c = 0;
for (int i = 0; i < size; i++){
if (str[i] == 'a'){
a = i + 1;
count -= min(b, c);
}
else if (str[i] == 'b'){
b = i + 1;
count -= min(a, c);
}
else{
c = i + 1;
count -= min(a, b);
}
}
return count;
}
int main(){
char str[] = "abcabbc";
int size = strlen(str);
cout<<"{'a', 'b', 'c'} 세 문자를 동시에 포함하지 않는 부분 문자열의 개수: "<<sub_without_all(str, size);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
{'a', 'b', 'c'} 세 문자를 동시에 포함하지 않는 부분 문자열의 개수: 15