[백준온라인] 32292번 ABB to BA (Easy)

백준 32292번 - ABB to BA (Easy) 🔤

🔗 문제 링크: https://www.acmicpc.net/problem/32292

32292번: ABB to BA (Easy)

---

📝 문제 요약

• 문자열 S가 주어집니다.
• 문자열 S는 'A'와 'B'로만 구성되어 있습니다.
• 문자열중 ABB는 BA로 치환된다. (연쇄 가능)

  ---

  
  

🧷 문제 분류

• 문자열
• 브루트포스

---

📦 제출 정보

🔗 소스코드: GitHub - cbkpar/BOJ/boj_32292.cpp

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
93878184	cbkpar	32292	맞았습니다!!	2024 KB	4 ms	C++17	461 B

---

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int iT;
	cin >> iT;
	for (int t = 1; t <= iT; ++t)
	{
		int iN;
		cin >> iN;

		string strWord;
		cin >> strWord;

		while (true)
		{
			if (strWord.find("ABB") == string::npos)
			{
				break;
			}
			strWord.replace(strWord.find("ABB"), 3, "BA");

		}
		cout << strWord << "\n";
	}
	return 0;
}

---

💡 풀이 방법

🔍 문제 접근

• "ABB"를 "BA"로 바꾸는 작업을 반복하여 더 이상 "ABB"가 없을 때 문자열을 출력하는 문제.
• 한 번의 치환이 또 다른 "ABB" 패턴을 생성할 수 있으므로 반복적인 탐색과 치환이 필요합니다.

🧠 핵심 아이디어

• find() 함수를 사용하여 문자열에서 "ABB"를 찾고, replace()로 "BA"로 치환합니다.
• 이 과정을 "ABB"가 더 이상 발견되지 않을 때까지 반복합니다.
• 모든 테스트 케이스에 대해 위의 작업을 수행한 후 최종 문자열을 출력합니다.

⚙️ 구현 방식

1. 테스트 케이스 개수 T를 입력받습니다.
2. 각 테스트 케이스마다 문자열을 입력받습니다.
3. while 반복문을 사용해 문자열에 "ABB"가 존재하는지 확인하고, 있다면 replace를 수행합니다.
4. 최종 변환된 문자열을 출력합니다.

✅ 시간 복잡도

• 각 find(), replace() 연산은 O(N)
• 반복 횟수를 K라고 하면 전체 시간 복잡도는 O(K × N)
• 실제 데이터에선 K가 작기 때문에 충분히 빠르게 동작합니다

  ---

🧪 예제 입력 / 출력

📘 예제 1

입력

3
3
ABB
9
ABABABBBB
12
AAAAAABBBBBB

출력

BA
BAABA
AAAABABA