[C++][BOJ] 9935 문자열 폭발 :: 문자열 비교(stack, erase)

폭발, 짝짓기 문제는 stack을 떠올리자.

 

[문제]

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

 

문자열에 폭발 문자열이 있다.

폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보자. 남아있는 문자가 없는 경우 "FRULA"를 출력하자.

 

문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

폭발 문자열의 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

 

[풀이]

문자열의 길이가 매우 기므로, 완전탐색으로는 풀 수 없다.

문자열 비교를 위해 stack 자료구조나 erase 함수를 이용하여 for문 하나로 끝내야 한다.

 

1번 풀이

1. stack을 이용해서 stack 크기가 폭발 문자열 크기보다 커졌으면 비교 시작한다.
2. stack 의 맨 위 글자와 폭발 문자열의 맨 끝자가 같은지 확인한다.
3. 같다면 폭발 문자열 길이만큼 빼서 stack 앞의 문자열 비교한다.
4. 3에서 stack 문자열은 뒤집어져 있으니까 reverse 함수로 뒤집는다.
5. 다르면 다시 집어넣는다. 같으면 뺀 상태이므로 넘긴다.
6. stack에 들어있는 문자열을 출력하면 끝.

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


//폭발, 짝짓기 => stack

int main() {
	string origin_str, bumb_str, answer_str = ""; //Input 문자열, 폴발 문자열, 정답 문자열
	stack<char> stk; // 폭발 문자열과의 비교를 위한 stack

	cin >> origin_str >> bumb_str;

	//stack 을 이용한 문자열비교
	for (char s : origin_str) {
		stk.push(s); // 일단 stack 에 문자열 차례로 넣기
		
		if (stk.size() >= bumb_str.size()) { //stack 크기가 폭발 문자열 크기보다 커졌으면 비교 시작
			char stack_end = stk.top(); // stack 의 맨 위 글자와
			char bumb_end = bumb_str[bumb_str.size() - 1]; // 폭발 문자열의 맨 끝자가 같은지 확인

			if (stack_end == bumb_end) { // 같다면 폭발 문자열 길이만큼 빼서 stack 앞의 문자열 비교
				string compare_str = "";
				for (char i : bumb_str) {
					compare_str += stk.top();
					stk.pop();
				}
				reverse(compare_str.begin(), compare_str.end()); // stack 문자열은 뒤집어져 있으니까 한번 뒤집기
				if (bumb_str != compare_str) { //다르면 다시 집어넣기 같으면 뺀 상태임
					for (int i : compare_str) {
						stk.push(i);
					}
				}
			}
		}
	}

	//출력
	if (stk.size() == 0) cout << "FRULA";
	else {
		while (stk.size()) {
			answer_str += stk.top(); stk.pop();
		}
		reverse(answer_str.begin(), answer_str.end());// stack 문자열은 뒤집어진 상태니까 한번 뒤집기
		cout << answer_str;
	}

	return 0;
}

 

*2번 풀이

1. 일단 입력 문자열을 하나씩 정답 문자열에 넣는다.
2. 정답 문자열이 폭발 문자열보다 길이가 크거나 같아지면 비교를 시작한다.
3. 폭발 문자열 길이만큼 뒷 글자 추출한다.
4. 추출한 문자열과 폭발 문자열이 확인한다. 같으면 erase 함수로 제거한다.

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

const string NULL_TEXT = "FRULA";

int main() {
	string origin_str, bumb_str, answer_str = "";

	cin >> origin_str >> bumb_str;

	for (char s : origin_str) {
		answer_str += s; 
		if (answer_str.size() >= bumb_str.size()) { 
			string end_str = answer_str.substr(answer_str.size() - bumb_str.size(), bumb_str.size()); 
			if (end_str == bumb_str) {
				answer_str.erase(answer_str.end() - bumb_str.size(), answer_str.end());
			}
		}
	}
	if (answer_str.size()) cout << answer_str << "\n";
	else cout << NULL_TEXT << "\n";

	return 0;
}