[Gold 5] 12904 A와 B

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

12904번: A와 B

 

이 문제는 그리디 알고리즘을 사용하면 해결할 수 있다.

 

처음에 문제에 접근하였을 때 S를 T로 만들기만 하면 된다고 생각하였다.

가능한 방법은 2가지 방법인 S뒤에 A를 추가하거나 S를 뒤집고 B를 추가하는 방법만 존재한다.

따라서 S를 먼저 큐에 삽입한 후 큐에서 문자열 하나를 뽑는다.

2가지 방법대로 문자열을 수정한 후 다시 큐에 문자열들을 삽입한다.

이때 문자열의 길이가 T와 같아진다면 반복을 멈추고, 문자열이 T와 같다면 1을 출력하도록하였다.

 

이 방식은 문자열 S의 길이가 최소 크기이고 T의 크기가 최대 크기인 경우 수 많은 경우의 수가 필요하기 때문에 큐의 크기가 엄청나게 커지게되어 메모리 초과가 발생하였다.

 

따라서 이 문제를 해결하기 위해 아래와 같은 방법을 사용하였다.

B와 ABBA가 입력으로 들어 왔다면 

B와 ABBA의 문자열 길이가 동일해질 때 까지 반복을 시작한다.

이때 ABBA의 마지막 문자가 B인 경우 마지막 문자를 제거하고 문자열을 뒤집는다.

만약 아니라면 마지막 문자만 제거한다.

ABBA => ABB
ABB => BA
BA => B

B == B   // result = 1

 

다른 예시를 적용하면 다음과 같다.

AB
ABB

ABB => BA

AB != BA  // result = 0

 

문자열의 마지막 문자를 제거하기 위해서는 pop_back()이라는 함수를 사용하면 손쉽게 제거할 수 있으며, 문자열을 뒤집는 것은 algorithm의 reverse함수를 사용하면 된다.

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

string S, T;
int result = 0;

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

	cin >> S;
	cin >> T;
	
	while (S.length() != T.length()) {
		if (T[T.length() - 1] == 'B') {
			T.pop_back();
			reverse(T.begin(), T.end());
		}
		else {
			T.pop_back();
		}
	}
	if (S == T) result = 1;

	
	cout << result << '\n';
}