백준[BOJ] 12904번(A와 B) C++

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

---

문제 설명

A와 B로 이루어진 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다.
문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

1. 문자열의 뒤에 A를 추가한다.
2. 문자열을 뒤집고 뒤에 B를 추가한다.

두 가지 연산만으로 S를 T로 바꿀 수 있으면 1을 출력하고 없으면 0을 출력한다.

Ex)

1. B와 ABBA가 주어졌을 때, 1번 연산에 의해 A를 추가해 BA가 된다.
   B->BA
2. BA에서 문자열을 뒤집고 B를 추가하면 ABB가 된다.
   B->BA->ABB
3. ABB에서 A를 추가하면 ABBA가 된다.
   B->BA->ABB->ABBA

---

문제 접근

문제를 보고서 처음 든 생각은 S에서 문자열을 추가해 T를 만들 생각을 하지말고 T에서 문자열을 삭제하가며 S를 만들 생각을 했다.
그래야지 주어진 2가지 연산을 하기 위한 조건을 판별하기 쉬웠다.
B에서 ABBA를 만든다고 하면 어떤 연산을 해야지 ABBA를 만들지 모르지만, ABBA에서 B를 만드는 것은 이미 만들어진 ABBA에서 B를 만드는 것은 경우의 수도 적고 더 쉽기 때문이다.
따라서 ABBA의 문자열의 뒤에서부터 비교해가며 만약 A면 A를 삭제만 해주고, 만약 B면 B를 삭제해주고 문자열을 뒤집어준다.

골드 문제라 걱정했지만 의외로 쉽고 생각하기도 쉬워서 해볼만하다고 생각했다.

---

C++ code

#include <iostream>
#include <algorithm>
using namespace std;

//A와 B
int main() {
	string S;
	string T;
	cin >> S >> T;  //문자열을 입력받는다.
	int i = T.length()-1;   //문자열 T의 끝에서부터 접근해야하므로 인덱스 i를 T의 문자열의 길이에서 1을 빼준다.
	while (T.length() != S.length()) {   //S와 T의 길이가 같아질때까지 반복문 돌기
		if (T[i] == 'A') {          //T의 뒤에서부터 만약 T의 마지막 문자열이 A라면
			T.pop_back();       //A를 삭제해준다.
		}
		else if (T[i] == 'B') {      //만약 T의 마지막 문자열이 B라면
			T.pop_back();         //B를 삭제해주고
			reverse(T.begin(), T.end());    //T의 문자열을 뒤집어준다.
		}
		i -= 1;          //인덱스를 줄여가며 T 문자열의 마지막부터 처음까지 반복한다.
	}
	if (S == T)     //T에서 삭제해 나아갔을때, S와 같다면
		cout << 1;     //1출력
	else
		cout << 0;
}