[BOJ] 12904번_A와 B_문자열 (C++)

[문제]

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

A와 B로만 이루어진 문자열 S와 T를 입력받고, S를 T로 바꿀 수 있는지 확인하는 문제이다.
S에는 "문자열의 뒤에 A를 추가한다.", "문자열을 뒤집고 뒤에 B를 추가한다." 라는 2가지 연산만 가능하다.

[사용 알고리즘]

문자열

[풀이 핵심]

• S를 T로 만드는 문제지만 S를 T로 만드는 것이 아니라 T를 S로 만든다고 생각하면 훨씬 쉽게 해결할 수 있다.
• T문자열의 마지막 문자가 A면 마지막 문자를 지우고, B면 마지막 문자를 지우고 algorithm헤더의 reverse함수를 사용해서 문자열을 뒤집으면 된다.
• 그렇게 T문자열의 뒤부터 시작해서 맨 앞까지 연산을 진행해주고 S문자열과 같아지면 S를 T로 만들 수 있는 것이다.

[코드]

//boj12904번_A와 B_구현

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main() {
	string S, T;
	cin >> S;
	cin >> T;

	bool check = false;

	for (int i = T.size() - 1; i >= 0; i--) {
		if (T[i] == 'A') {
			T.erase(T.begin() + i);
		}
		else if (T[i] == 'B') {
			T.erase(T.begin() + i);
			reverse(T.begin(), T.end());
		}

		if (S == T) {
			check = true;
		}
	}

	if (check) {
		cout << 1;
	}
	else {
		cout << 0;
	}
}