C++ 문자열에서 'abc' 부분 수열의 최대 제거 횟수 구하기

이번 문제는 문자열에서 주어진 부분 수열(subsequence)을 제거할 수 있는 최대 횟수를 구하는 것입니다. 하나의 문자열 s가 주어졌을 때, 이 문자열에서 'abc'라는 부분 수열을 최대 몇 번까지 제거할 수 있는지 찾아야 합니다.

문제 이해하기

예시를 통해 문제를 자세히 살펴보겠습니다.

입력

s = 'dnabcxy'

출력

설명 − 주어진 문자열('dnabcxy')에서 'abc' 부분 수열은 한 번만 발견할 수 있으므로 출력은 1입니다.

입력

s = 'zcabcxabc'

출력

2 ('zcabcxabc')

풀이 접근 방식

Max() 함수에서 int 타입의 변수 i, a, ab, abc를 모두 값 0으로 초기화합니다.
i = 0부터 i < s.length()까지 반복문을 실행합니다.
반복문 안에서 s[i] == 'a'인지 확인하고, 참이라면 a 값을 1 증가시킵니다. 이는 잠재적인 'abc' 수열의 시작점을 하나 확보한 것입니다.
그렇지 않고 s[i] == 'b'인 경우에는 a > 0 조건을 추가로 검사합니다. 두 조건이 모두 참이면 a를 1 감소시키고 ab를 1 증가시킵니다. 즉, 앞서 찾은 'a' 뒤에 'b'가 이어져 "ab" 쌍이 완성된 것입니다.
마지막으로 s[i] == 'c'인 경우에는 ab > 0 조건을 검사합니다. 두 조건이 모두 참이면 ab를 1 감소시키고 abc를 1 증가시킵니다. 이는 "ab"에 'c'가 이어져 완전한 "abc" 부분 수열 하나가 완성되었음을 의미합니다.
반복문이 종료되면 abc 값을 반환합니다. 이 값이 곧 문자열에서 제거할 수 있는 'abc' 부분 수열의 최대 개수입니다.

이 알고리즘은 그리디(greedy) 방식으로 동작합니다. 문자열을 한 번만 순회하면서 'a' → 'ab' → 'abc' 단계별로 카운터를 옮겨 가기 때문에, 시간 복잡도는 O(n)으로 매우 효율적이며 공간 복잡도 역시 O(1)에 불과합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int Max(string s){
    int i=0, a=0, ab=0, abc=0;
    for (i = 0; i < s.length(); i++){
        if (s[i] == 'a'){
            a++;
        }
        else if (s[i] == 'b'){
            if (a > 0){
                a--;
                ab++;
            }
        }
        else if (s[i] == 'c'){
            if (ab > 0){
                ab--;
                abc++;
            }
        }
    }
    return abc;
}
//main function
int main(){
    string s = "zcabcxabc";
    cout << Max(s);
    return 0;
}