백준 32293 (C++) ABB to BA (Hard)

최초 업로드: 2025-11-20 20:30:55

최근 수정 시간: 2025-11-20 20:30:55

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] ABB to BA (Hard)

[문제 링크](https://www.acmicpc.net/problem/32293)

## 문제 설명

이 문제는 "ABB to BA"의 어려운 버전입니다. 두 버전은 $t$와 $n$의 제한을 제외하고 동일합니다.

<code>'A'</code>와 <code>'B'</code>만으로 이루어진 문자열 $S$가 주어집니다. 여러분은 다음 동작을 더 이상 수행할 수 없을 때까지 반복해야 합니다.

반복이 끝난 후 $S$의 내용을 출력하는 프로그램을 작성해 주세요.

## 입력

각 입력은 여러 개의 테스트 케이스로 구성됩니다. 입력의 첫 번째 줄에 테스트 케이스의 개수 $t$가 주어집니다. ($1 \le t \le 5 \cdot 10^4$)

이후 테스트 케이스의 정보가 주어지며, 각 테스트 케이스의 입력은 다음과 같이 두 줄로 구성됩니다.

<ul>
	<li>첫 번째 줄에 $S$의 길이를 나타내는 정수 $n$이 주어집니다. ($1 \le n \le 5\cdot 10^5$)</li>
	<li>두 번째 줄에 길이 $n$의 문자열 $S$가 주어집니다. ($S_i$는 모두 <code>'A'</code> 또는 <code>'B'</code>)</li>
</ul>

모든 테스트 케이스에 대한 $n$의 합이 $5\cdot 10^5$을 초과하지 않습니다.

## 출력

각 테스트 케이스에 대해 반복이 끝난 후 $S$의 내용을 한 줄에 출력합니다.

## 풀이
스택에 문자 1개씩 넣으면서 ABB가 들어가면 BA로 바꿔 넣으면 됩니다. 만약 연쇄 반응이 일어나면, B 1개와, 그 횟수만큼의 A가 뒤에 추가됩니다.

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

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 while(t--) {
 int n; string s; cin >> n >> s;
 vector<char> stk;
 for(char ch:s) {
 if(ch=='A') {
 stk.push_back('A');
 } else {
 int cnt=0;
 while(stk.size()>=2 && stk[stk.size()-2]=='A' && stk[stk.size()-1]=='B') {
 cnt++;
 stk.pop_back();
 stk.pop_back();
 }
 stk.push_back('B');
 while(cnt--) stk.push_back('A');
 }
 }
 for(char ch:stk) cout << ch;
 cout << '\n';
 }
}
```