[백준] 문자열 폭발 (9935번)

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

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

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

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

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

예제 입력 1 복사

mirkovC4nizCC44 C4

예제 출력 1 복사

mirkovniz

예제 입력 2 복사

12ab112ab2ab 12ab

예제 출력 2 복사

FRULA

---

문자열 처리 문제이다. 까다로운 문제였다.

원본 문자열을 정답 문자열에 한 글자씩 옮기면서 현재 글자가 폭탄 문자열의 끝 문자와 같다면 앞으로 돌아가면서 폭탄 문자열이 포함되는지를 검사한다. 

포함되어있다면 pop_back()함수를 통해 폭탄 문자열을 제거하고 계속 검사한다.

 

검사 결과가 빈 문자열이라면 FRULA를 출력하고 아니라면 문자열을 그대로 출력한다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%AC%B8%EC%9E%90%EC%97%B4%20%ED%8F%AD%EB%B0%9C%20(9935%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

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

int main()
{
	cin >> str >> bomb;
	int sLen = str.length();
	int bLen = bomb.length();

	for (int i = 0; i < str.size(); i++) {
		ans += str[i];
		if (str[i] == bomb[bLen - 1] && i >= bLen - 1) {
			bool isPossible = true;
			for (int j = 0; j < bLen; j++) {
				if (ans[ans.size() - bLen + j] != bomb[j]) {
					isPossible = false;
					break;
				}
			}
			if (isPossible) {
				for (int j = 0; j < bLen; j++) ans.pop_back();
			}
		}
	}
	if (!ans.empty())
		cout << ans;
	else
		cout << "FRULA";
}