[BOJ 25381] ABBC

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

25381번: ABBC

 

- 문제 요약

 

A, B, C로만 이루어졌고, 길이가 |S|인 문자열 S가 있다.

이 문장열에 대해 아래와 같은 시행을 할 수 있다.

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

각 문자는 최대 한 번만 지울 수 있다.

문자열 S가 주어졌을 때, S에 대한 최대 시행 횟수를 구해라.

 

 

- 알고리즘 정리

 

문제에서 제공하는 예제 테스트 케이스를 보고 B를 가장 많이 지울 때 최대 횟수가 될 것이라고 추측해 봤습니다.

(아래는 문제에서 제공되는 예제 테스트 케이스에 대한 아이디어)

 

1번 A와 2번 B를 지운다. 이 경우 시행의 횟수는 1번이고, 남은 문자열은 CBA이다. 어떤 두 문자를 골라도 시행의 조건을 만족시킬 수 없으므로, 더 이상 시행을 할 수 없다.
1번 A와 4번 B를 지우고, 이어 2번 B와 3번 C를 지운다. 이 경우 시행의 횟수는 2번이고 남은 문자열은 A이다. 문자열에 남은 문자가 하나이므로, 더 이상 시행을 할 수 없다.

 

그래서 앞에서부터 순서대로 B를 지우며 그리디 하게 처리해 줬습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

string s;
bool check[300001];
queue<int>q;
int result,co;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='B'){
			q.push(i);
		}
		else if(s[i]=='C'&&!q.empty()){
			check[q.front()]=true;
			q.pop();
			result++;
		}
	}
	q=queue<int>();
    for(int i=0;i<s.length();i++){
        if(s[i]=='A'){
        	co++;
		}
        else if(s[i]=='B'&&co&&!check[i]){
            check[i]=true;
            co--;
            result++;
        }
    }
    cout<<result;
}

코드 제출 결과