백준 12904 c++ "A와 B" -PlusUltraCode-

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

 

[필자 사고]

bfs 탐색을 하게 되면 말도 안되는 시간초과가 난다. 당여한 결과이다. 2^1000승은 말도 안되기 때문이다. 자세히 문제를 관찰하면 해당 문제는 그리디 탐색 즉 탐욕적 알고리즘을 통해 해결 된다는걸 알게 된다. 결국 정해진 결과는 하나이다.

 

S에서 T로 가지말고 T에서 S로 가는 생각을 하게 되면 해결할 수 있다.

이미 만들어진 T의 마지막 문자열은 결정되어 있는거다. 

그래서 A라는 문자열이 있으면 해당 A를 지우고 

B라는 문자열이 있으면 B를 지우고 뒤집으면 된다.

 

아래는 자세한 코드해설이다.

[코드 해설]

1. 프로그램 개요

이 프로그램은 문자열 변환 문제를 해결한다. 주어진 두 문자열 str1과 str2에 대해, str2에서 특정 규칙에 따라 문자를 제거하거나 뒤집는 연산을 반복해서 str1을 만들 수 있는지를 판단한다. 만들 수 있다면 1, 불가능하다면 0을 출력한다.

---

2. 입력 처리 함수 (Input 함수)

Input() 함수는 두 개의 문자열 str1과 str2를 표준 입력으로부터 받아 저장한다. 이후 두 번째 문자열 str2의 각 문자를 덱(deque<char>) 자료구조에 삽입한다. 이 덱은 문자열 변환 과정에서 문자를 앞뒤로 제거하거나 순서를 뒤집는 데 사용된다.

---

3. 문자열 일치 확인 함수 (checkWords 함수)

checkWords() 함수는 현재 덱에 저장된 문자들의 나열이 문자열 str1과 동일한지를 검사한다.

• 먼저 덱과 str1의 길이가 같은지 확인한다.
• 길이가 같다면, 각 문자 위치를 하나씩 비교하여 모두 일치하는지 확인한다.
• 일치하면 true, 하나라도 다르면 false를 반환한다.
  이 함수는 변환이 성공적으로 완료되었는지를 판별하는 데 사용된다.

---

4. 게임 시작 함수 (Game_Start 함수)

Game_Start() 함수는 문자열 변환 과정을 시뮬레이션한다. 다음과 같은 규칙을 반복 적용한다:

• 덱이 비어 있지 않은 동안 반복한다.
• 현재 덱이 str1과 정확히 일치하는지 checkWords()로 검사한다. 일치하면 1을 출력하고 함수 종료.
• 덱의 마지막 문자가 'A'라면 해당 문자를 단순히 제거한다.
• 덱의 마지막 문자가 'B'라면 해당 문자를 제거하고, 이후 덱 전체를 뒤집는다.

이 과정은 str2에서 시작해 가능한 모든 변환을 거쳐 str1을 만들 수 있는지를 판단한다. 변환이 모두 끝날 때까지 str1을 만들지 못하면 최종적으로 0을 출력한다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

string str1, str2;
deque<char> myDeque;
void Input() {
	cin >> str1 >> str2;
	for (int i = 0; i < str2.size(); i++) {
		myDeque.push_back(str2[i]);
	}

	
}

bool checkWords(string str, deque<char>& myDeque) {
	if (myDeque.size() == str.size()) {
		for (int i = 0; i < myDeque.size(); i++) {
			if (myDeque[i] == str[i])continue;
			else {
				return false;
			}
		}
		return true;
	}
	return false;
}

void Game_Start() {
	while (!myDeque.empty()) {
		int endIdx = myDeque.size() - 1;
		
		if (checkWords(str1, myDeque) == true) {
			cout << 1;
			return;

		}

		if (myDeque[endIdx] == 'A') {
			myDeque.pop_back();
		}
		else {
			myDeque.pop_back();
			reverse(myDeque.begin(), myDeque.end());
		}
	}

	cout << 0;
}

int main(void) {
	Input();
	Game_Start();
}