[백준][C++] 9935: 문자열 폭발

문제 링크: https://www.acmicpc.net/problem/9935

 

문자열 안에 폭탄 문자열이 있으면 연쇄적으로 계속 없어집니다. 뿌요뿌요같은 거라고 생각하면 됩니다

스택을 사용하면 간단하게 풀 수 있습니다.

스택에 문자열을 앞글자부터 계속 차례대로 넣는데, 폭탄 문자열의 마지막 글자 문자를 넣는 경우 폭탄 문자열 길이만큼 스택에서 빼서 폭탄 문자열인지 검사합니다. 폭탄 문자열이면 버리고, 아니면 다시 스택에 그대로 넣습니다.

그러면 나중에 스택에는 폭발이 연쇄적으로 끝난 문자열만 들어있겠죠? 전부 꺼내서 reverse 해주면 문자열이 됩니다.

문자열 뒤집는거만 잘 해주면 쉬운 문제입니다

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>
using namespace std;



int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	string s, bomb;
	cin >> s >> bomb;


	stack<char> st;
	for (auto& c : s) {
		st.push(c);
		if (c == bomb.back() && st.size() >= bomb.size()) {
			string snippet;
			for (int i = 0; i < bomb.size(); ++i) {
				snippet += st.top();
				st.pop();
			}
			
			reverse(snippet.begin(), snippet.end());
			if (bomb != snippet) {
				for (auto& c: snippet)
					st.push(c);
			}
		}
	}

	if (st.empty())
		cout << "FRULA\n";
	else {
		string out;
		while (!st.empty()) {
			out += st.top();
			st.pop();
		}
		reverse(out.begin(), out.end());
		cout << out << '\n';
	}

	return 0;
}