백준 9935 - 문자열 폭발(C++)

문제

문자열이 하나와 폭발 문자열이 하나 주어진다.

 

문자열에 폭발 문자열이 포함되고 있는 경우, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.

 

이때 폭발 문자열이 남지 않을 때 까지 이를 반복하여 최종적으로 남은 문자열을 출력하는 문제다.

 

만약 아무런 문자도 남지 않은 경우 "FRULA"를 출력한다.

 

입력

두 개의 문자열이 차례대로 입력된다.

 

예제 입력

mirkovC4nizCC44
C4

 

예제 출력

mirkovniz

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

애초에 이 문제는 문제 설명 자체에서 힌트를 준 것이나 다름이 없다. 폭발 문자열를 만났을 때 해당 문자열은 없애고 새로 만들어진 문자열을 다시 검사하고 또 이를 반복하는 것이기 때문이다.

 

이를 그대로 코드로 옮기면 문제를 해결할 수 있다.

 

이때, 새로 만들어진 문자열을 어떻게 처리할 수 있냐가 문제인데, 문자를 차례대로 스택에 저장했다가 폭발 문자열을 만났을 때 스택에서 지우는 형식으로 풀 수 있다.

 

코드

#include <iostream>
#include <vector>
#include <string>

std::string solveStr(std::string str, std::string cmp)
{
	std::string temp = "";
	bool flag = false;
	int size = 0;
	int cmpLen = cmp.length();
	for (int i = 0; i < str.size(); i++)
	{
		temp += str[i];
		flag = false;
		if (temp.size() >= cmpLen)
		{
			for (int j = 0; j < cmpLen; j++)
			{
				if (temp[temp.size() - cmpLen + j] != cmp[j])
					break;
				if (j == cmpLen - 1)
					flag = true;
			}
			if (flag)
				temp.erase(temp.end() - cmpLen, temp.end());
		}
	}
	if (temp.size() == 0)
		return "FRULA";
	return temp;
}

int main(void)
{
	std::string str, cmp;
	std::cin >> str >> cmp;
	std::cout << solveStr(str, cmp) << std::endl;
	return 0;
}

 

문제 출처

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

9935번: 문자열 폭발