[백준 / C++] 12904번: A와 B

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

12904번: A와 B

 

난이도: solved.ac 골드 5

 

알고리즘 분류

구현, 그리디 알고리즘, 문자열

 

접근 방법

S에서 T로 만들려고 하지 말고, T를 S로 만들려고 하면 매우 간단해진다.

 

문자열을 바꿀 때는 아래의 두 가지 연산만 가능한데, 여기에 포인트가 있다.

 

- 문자열의 뒤에 A를 붙인다.

- 문자열을 뒤집고 뒤에 B를 붙인다.

 

결국에는 맨 뒤의 문자가 A인지 B인지만 보면 전의 문자열이 뭐였는지 알 수 있게 된다.

 

구현

문자열을 실제로 뒤집고 하나씩 지우는 과정은 시간 복잡도를 크게 만들 것 같아서 투 포인터 방식으로 풀었다.

 

T에서 맨 앞 문자를 가리키는 포인터를 st, 맨 뒤 문자를 가리키는 포인터를 en라고 두고

 

문자 하나씩 지워가는 과정은 en을 앞으로 한 칸 당기는 형식으로 구현했다.

 

문자열을 뒤집어야 할 때는 st와 en의 위치를 서로 바꾸었다.

 

코드

#include <bits/stdc++.h>
using namespace std;
string A, B;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> A >> B;
	int st = 0, en = B.size() - 1;
	int i, tmp;
	while (abs(en - st) + 1 > A.size()) {
		if (B[en] == 'B') {
			if (st < en)
				en--;
			else
				en++;
			tmp = st;
			st = en;
			en = tmp;
		}
		else {
			if (st < en)
				en--;
			else
				en++;
		}
	}
	for (i = 0; i < A.size(); i++) {
		if (A[i] != B[st])
			break;
		if (st < en)
			st++;
		else
			st--;
	}
	if (i == A.size())
		cout << 1;
	else
		cout << 0;
}

 

성능

코드 제출 결과