백준 Gold 3 ABBC

ABBC (백준 Gold 3)

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

A B C 로만 이루어진 문자열 s가 존재할때
다음과 같은 시행을 할 수 있다

• A 와 뒤의 B를 제거
  
• B 와 뒤의 C를 제거
  

s에 시행할 수 있는 시행의 최대 횟수를 구하는 문제

풀이 방법

일단 B를 ‘먼저’ 제거하는 경우
C를 제거할 수 없으므로

조건에 맞는 B와 C를 최대한 제거한 후
A와 B를 제거하는 시행을 실행해야 한다

-> 그리디

이후로는
‘큐’를 통하여
각각의 A B C 를 담고,
(이 때, 각각의 ‘인덱스’도 같이 pair로 챙긴다)

각각의 큐에서
BC 제거 과정 -> AB 제거 과정을 진행하면 풀 수 있다!

• ‘B’ 의 ‘앞’ 부분과 ‘C’의 앞 을 비교하여
  B의 인덱스가 더 작으면 둘다 제거하기
  아니라면 ‘해당’하는 C는 조건에 맞는 B가 없는 것이므로
  폐기한다
  

• A B 부분도 같은 방식으로 진행
  

제출 코드

#include<iostream>
#include<queue>
#include<string>

using namespace std;

int main()
{
	string str;
	cin >> str;

	int answer = 0;
	queue<pair<int, char>> aq, bq, cq;

	for (int i = 0; i < str.size(); i++)
	{
		char c = str[i];

		if (c == 'C')
		{
			cq.push({ i,c });
		}
		else if (c == 'B')
			bq.push({ i,c });
		else
			aq.push({ i,c });
	}

	if (cq.size() > 0 &&
		bq.size() > 0)
	{
		while (cq.empty() == false &&
			bq.empty() == false)
		{
			if (bq.front().first < cq.front().first)
			{
				answer++;
				cq.pop();
				bq.pop();
			}
			else
			{
				cq.pop();
			}
		}
	}

	if (bq.size() > 0 &&
		aq.size() > 0)
	{
		while (aq.empty() == false &&
			bq.empty() == false)
		{
			if (aq.front().first < bq.front().first)
			{
				answer++;
				aq.pop();
				bq.pop();
			}
			else
			{
				bq.pop();
			}
		}
	}

	cout << answer;
}

결과

처음에 deque 나 stack을 사용하다
많은 착오가 있었다

그러다 생각해보니 각 문자의 ‘인덱스’가 중요하다고 생각하였고
이후, queue<pair<int,char»를 통해 풀 수 있었다