[백준] 9935 문자열 폭발

[백준] 9935 문자열 폭발

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

틀린 풀이

• 48%에서 시간 초과

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	string input;
	string bomb;

	cin >> input >> bomb;

	int inputLen = input.length();
	int bombLen = bomb.length();

	string answer = "";
	int answerLen = 0;

	for (int i = 0; i < inputLen; ++i) {
		answer += input[i];
		answerLen++;

		if (answerLen >= bombLen) {
			string subAnswer = answer.substr(answerLen - bombLen, bombLen);
			if (subAnswer == bomb) {
				answer = answer.substr(0, answerLen - bombLen);
				answerLen -= bombLen;
			}
		}
	}

	if (answer == "") cout << "FRULA";
	else cout << answer;

	return 0;
}

풀이

• 문자열 substring을 사용하는 대신, vector와 deque 이용

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	string input;
	string bomb;

	cin >> input >> bomb;

	int inputLen = input.length();
	int bombLen = bomb.length();

	//마지막으로 반환될 정답 문자열
	vector<char> answerV;
	//정답 문자열의 뒤에서부터 bombLen 길이의 문자열
	deque<char> recent;

	//recent와 비교용 폭발 문자열
	deque<char> bombDQ;
	for (int i = 0; i < bomb.size(); ++i) {
		bombDQ.push_back(bomb[i]);
	}

	for (int i = 0; i < inputLen; ++i) {
		answerV.push_back(input[i]);
		recent.push_back(input[i]);

		if (recent.size() < bombLen) continue;
		if (recent.size() > bombLen) {
			recent.pop_front();
		}

		//recent.size() == bombLen
		if (recent == bombDQ) {
			recent.clear();
			for (int i = 0; i < bombLen; ++i) {
				answerV.pop_back();
			}
			for (int i = 0; i < bombLen; ++i) {
				int idx = answerV.size() - i - 1;
				if (idx < 0) break;
				recent.push_front(answerV[idx]);
			}
		}
	}
	if (recent == bombDQ) {
		recent.clear();
		for (int i = 0; i < bombLen; ++i) {
			answerV.pop_back();
		}
	}

	string answer = "";
	for (int i = 0; i < answerV.size(); ++i) {
		answer += answerV[i];
	}
	if (answer == "") cout << "FRULA";
	else cout << answer;

	return 0;
}