[baekjoon 12904] A와 B (문자열, 그리디) (C++)

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

12904번: A와 B

시작 단어에서 뒤에 A를 붙이거나, 단어를 뒤집어서 B를 붙이거나 해서 목표 단어까지 만들 수 있는지의 여부를 계산해내는 문제이다.

 

처음엔 아무 생각 없이 DFS로 매번 A를 붙이거나, B를 붙였더니 시간 초과가 났다.

그도 그럴 것이, 시작 단어가 1글자에서 시작하고 목표 단어가 1000 글자면 매 단계마다 2번 ^ 1000이다.

4글자 단어를 만드는데 2^0 + 2^1 + 2^2 + 2^3 = 2^4 - 1번의 함수 호출이 필요하다.

1000 길이의 문자열을 만드는데 대략 2^1000의 계산이 필요할 것이다.

 

따라서, 생각을 바꿔서 그리디 하게 목표 단어에서 시작 단어로 만들어보면 되지 않을까?

 

목표 단어의 끝이 B로 끝나면 B를 지워주고 단어를 뒤집어준다.

끝이 A로 끝나면 그냥 A만 지워준다.

그리고 시작 단어와 비교해서 맞으면 종료해주면 된다.

 

이 방법의 최악은 시작 글자는 1글자, 목표 글자는 1000 글자가 모두 B로 된 "BBBBBB... BB"일 것이다.

매번 삭제하고, reverse 해줘야 하기 때문이다.

그래도 O(N^2)으로 판단된다. 매 글자 수 * reverse 연산.. (reverse 연산도 결국 문자열을 하나하나 뒤집어야 하니 o(n)이 아닐까?)

#include <iostream>
#include <algorithm>

using namespace std;

string A, B;
int flag = false;

// 목표를 만들어가지말고 목표를 역으로 바꾸면서 시작점이 될 수 있는지 그리디하게 접근하자

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> A >> B;
	
	while (B.size() > 0) {
		if (B.back() == 'B') {
			B.erase(B.end() - 1);
			reverse(B.begin(), B.end());
		}
		else
			B.erase(B.end() - 1);

		if (B == A) {
			flag = true;
			break;
		}
	}

	if (flag)
		cout << 1;
	else
		cout << 0;
}