boj 25381 ABBC

https://www.acmicpc.net/problem/25381

 

- A와 그 뒤에 있는 B를 지운다.

- B와 그 뒤에 있는 C를 지운다.

문자열을 지울 수 있는 두 가지 방법입니다.

여기서 B가 중복되었다는 것을 이용할 수 있습니다.

 

1. A보다 뒤에 있는 B를 지울때 최대한 뒤에 있는 B를 지우거나

2. C보다 앞에 있는 B를 지울때 최대한 앞에 있는 B를 지우거나

둘 중 하나를 먼저 진행하시면 이 문제를 해결할 수 있습니다.

 

저는 2번 방법으로 문제를 풀었습니다.

문자열을 한 번 순회하면서 B를 만나면 queue에 넣고, C를 만나면 queue에 있는 B를 하나 제거합니다.

이때 queue에는 B의 인덱스를 넣었고, 가장 앞의 인덱스가 먼저 제거됩니다.

 

그렇게 BC 를 모두 지웠으니 이제 AB를 지우도록 합니다.

BC 조합을 먼저 지웠기 때문에 queue에 들어있는 B를 그냥 지워주시면 됩니다.

여기서 주의할건 현재 순회중인 인덱스보다 낮은 인덱스가 queue에 있다면 먼저 제거해야 합니다.

 

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;
 
queue<int> q;
string str;
int len;
 
void func() {
    int ret = 0;
    for (int i = 0; i < len; i++) {
        if (str[i] == 'B') q.push(i);
        else if (str[i] == 'C') {
            if (q.empty()) continue;
            q.pop();
            ret++;
        }
    }
 
    for (int i = 0; i < len && !q.empty(); i++) {
        while (!q.empty() && q.front() < i) q.pop();
        if (str[i] == 'A') {
            if (q.empty()) continue;
            q.pop();
            ret++;
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> str;
    len = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}