문제

문제 링크

해설

■ 공통

• 문자열의 길이가 최대 100만입니다. 따라서 2중 for문을 사용한 bruteforce O(n²) 알고리즘을 사용하면 시간초과가 납니다.
• 문제 풀이의 핵심은 폭발문자열을 만났을 때, 연쇄폭발을 효과적으로 처리하는 것입니다.
  • 예를 들어, 폭발문자열이 C4일 때, CCC444 라는 문자열이 있을 때,
  • CCC444 → CC44 → C4 →
    이런 식으로 n번 폭발이 일어나는 것이 아니라,
  • CCC444 →
    이렇게 바로 한 번에 폭발이 일어나도록 효율적으로 폭발을 처리해야 합니다.
• 문제를 푸는 방법은 총 2가지 입니다.

① 문자열 내장함수 이용

• 문자열 내장함수 또는 <algorithm> 헤더파일의 find()는 함정입니다. find()는 O(n)입니다. 따라서 find()를 사용하면 O(n²)이 됩니다.
• 문자열을 저장할 외부 공간 temp을 하나 만듭니다.
• 문자열 A를 입력받은 뒤 한 글자씩 읽어 temp에 넣습니다.
• temp의 문자열의 길이가 폭발문자열의 길이 이상일 때부터, 뒤에서부터 폭발문자열과 비교합니다.
• 일치하면 .erase() 내장함수를 이용해서 문자열을 지웁니다.
• 문자열 A의 끝까지 이를 반복하면 O(n) 알고리즘으로 해결할 수 있습니다.

② 스택 이용

• 근본적인 방법은 위 ①과 같습니다.
• 문자열 A를 한 글자씩 읽어 스택에 삽입합니다.
• 스택의 크기가 폭발문자열의 길이 이상일 때부터, 스택의 top() 문자가 폭발문자열의 끝문자와 같을 때, 폭발문자열의 길이만큼 pop() 해 문자열을 만듭니다.
• 이 문자열은 스택에서 꺼냈기 때문에 뒤집혀있을 것입니다. 따라서 reverse() 함수를 이용해서 다시 뒤집어 원상태로 만듭니다.
• 이를 폭발문자열과 비교합니다.
• 만일 폭발문자열과 다르다면, 다시 스택에 넣어줍니다.
• ① 보다 복잡하고 번거로워 보이지만, 더 빠릅니다.

코드

① 문자열 내장함수 이용

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

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	string str, bomb;
	cin >> str >> bomb;
	
	string temp = "";
	for (size_t i = 0, bombLen = bomb.size(); i < str.size(); ++i) {
		temp.push_back(str[i]);
		if (temp.size() < bombLen) continue;
		if (!bomb.compare(temp.substr(temp.size() - bombLen, bombLen)))
			temp.erase(temp.size() - bombLen, bombLen);
	}
	cout << ((temp.empty()) ? "FRULA" : temp) << '\n';
}

소스코드 링크

② 스택 이용

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

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	string str, bomb;
	cin >> str >> bomb;
	
	stack<char> stk;
	for (char& ch : str) {
		stk.push(ch);
		if (stk.size() >= bomb.size() && stk.top() == bomb.back()) {
			string temp = "";
			for (size_t i = 0; i < bomb.size(); ++i) {
				temp += stk.top();
				stk.pop();
			}
			reverse(begin(temp), end(temp));
			if (bomb != temp)
				for (const char& c : temp) stk.push(c);
		}
	}
	if (stk.empty()) cout << "FRULA\n";
	else {
		string answer = "";
		while (!stk.empty()) answer += stk.top(), stk.pop();
		reverse(begin(answer), end(answer));
		cout << answer << '\n';
	}
}

소스코드 링크

결과