백준 9935 문자열 폭발 c++

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

9935번: 문자열 폭발

생각보다 애먹은 문제였다.

골드4 + input길이 100만, 런타임 2초인 거 보면 그냥 무지성 find, substr 썼다간 시간초과다.

최대한 덜 검사하려면, input string 한바퀴 도는 내에 모든 bomb을 다 찾아서 없애야 한다.

stack <char> 두 개를 사용해서 해결했다.

 

23라인에 correctCnt를 한번 더 검사하는 로직이 없었어서 "bbomb" 이런 경우에 에러가 발생했다. <- 이놈이 20분 잡아 먹음

다 끝나고 매번 시스템콜인 cout을 호출하면 런타임 터지지 않을까 싶어서 char가 거꾸로 들어간 stack b를 출력해 주려 string에 담고 pop 하는 과정을 거쳤다.

 

 

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	string input, bomb;
	cin >> input >> bomb;
	int correctCnt = 0;
	stack<char>	a, b;

	for (int i = input.size() - 1; i >= 0; i--) // 문자열 뒤부터 스택에넣어줌
		a.push(input[i]);
	while (!a.empty()) {
		if (a.top() == bomb[correctCnt])
			correctCnt++;
		else {
			correctCnt = 0;
			if (a.top() == bomb[correctCnt])
				correctCnt++;
		}
		b.push(a.top());
		a.pop();
		if (correctCnt == bomb.size()) { // isbomb
			correctCnt = 0;
			for (int i = 0; i < bomb.size(); i++)
				b.pop();
			for (int i = 0; !b.empty() && i <= bomb.size() + 1; i++) {
            	// 여기서 bomb의 숫자만큼 돌아가줘야 bombombb 이런경우도 처리 가능하다.
				a.push(b.top());
				b.pop();
			}
		}
	}
	if (b.empty())
		cout << "FRULA";
	else {
		string s(b.size(), 0);
		for (int i = b.size() - 1; i >= 0; i--) {
			s[i] = b.top();
			b.pop();
		}
		cout << s;
	}
}