A와 B

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

문제 풀이 : 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임으로, 오직 두 가지 연산만이 가능하다는 것이 특징이다. 해당 두 가지 연산은 1) 문자열의 뒤에 A를 추가한다. 2) 문자열을 뒤집고 뒤에 B를 추가한다. 이다. 이 두가지 연산에서 중요하게 보아야할 점은 "해당 연산이 이루어지고 나서"이다. 1번 연산이 이루어지고 나면 문자열의 마지막은 A가 되고, 2번 연산이 이루어지고 나면 문자열의 마지막은 B가 된다. 즉, 어떤 연산이 진행되었는지에 대한 내용이 명확하게 보여진다는 의미이다. 그렇기에, 완성된 문자열인 T로부터 시작하여, 마지막 문자열의 값에 따라 위의 연산을 반대로 진행하는 방식으로 구현하였다.

사용 함수

• reverse(start, end) : algorithm헤더에 존재하는 함수로, 시작점과 끝점을 매개변수로 입력하면, 해당 구간 내에서의 순서를 뒤바꾸는 함수이다.
• substr(startpoint, length) : 전체 문자열에서 지정 길이의 문자열만을 추출할 때 쓰는 함수로 이 문제에서는 마지막 문자열을 제외한 문자열을 추출하기 위하여 사용한 함수이다.

소스 코드 :

#include <bits/stdc++.h>

using namespace std;

string a, b, temp;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> a;
	cin >> b;
	
	int i = 0;
	while(i < 3) {
		if(b[b.length() - 1] == 'B'){
			temp = b.substr(0, b.length() - 1);
			reverse(temp.begin(), temp.end());
		}
		else if(b[b.length() - 1] == 'A') {
			temp = b.substr(0, b.length() - 1);
		}
		b = temp;
		
		if(a.length() >= b.length()) {
			break;
		}
	}
	
	if(a == b) {
		cout << "1" << "\n";
	}
	else {
		cout << "0" << "\n";
	}
	
	return 0;
}

• 문제 출처 : https://www.acmicpc.net/problem/12904
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.텍스트