[BOJ] 9935번 | 문자열 폭발 (C++)

🔗문제 보러가기

9935번: 문자열 폭발

 

🧑‍💻풀이 과정

string을 스택(stack)처럼 사용하여 풀었습니다. 정답을 저장할 string 변수(answer)를 따로 준비한 후, 주어진 문자열을 차례대로 순회하였습니다.

 

그리고 다음과 같은 과정을 진행해 주었습니다.

1. 현재 읽은 문자열을 answer 변수에 넣습니다.
2. 현재 읽은 문자열이 폭발 문자열의 마지막 문자와 같다면, 다음 과정을 거칩니다.
   • answer와 폭발 문자열을 뒤에서부터 차례대로 읽으며 비교합니다.
   • 두 문자열이 서로 같다면, 폭발 문자열 크기만큼 answer에서 pop_back()을 해줍니다. 
3. 문자열 순회를 마친 후 answer가 비었다면 "FRULA"를, 아니라면 answer를 출력합니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <string>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

bool IsExplosionString(const string& explosionString, const string& targetString)
{
	if (targetString.size() < explosionString.size())
		return false;

	int targetIdx = targetString.size() - 1;
	for (int expIdx = explosionString.size() - 1; expIdx >= 0;)
	{
		if (targetString[targetIdx--] != explosionString[expIdx--])
			return false;
	}

	return true;
}

int main()
{
	FAST_IO
	string str, explosionString;
	cin >> str >> explosionString;

	string answer;
	for (const auto& character : str)
	{
		answer.push_back(character);

		if (character == explosionString.back())
		{
			if (!IsExplosionString(explosionString, answer))
				continue;

			for (int i = 0; i < explosionString.size(); i++)
				answer.pop_back();
		}
	}

	if (answer.empty())
		cout << "FRULA";
	else
		cout << answer;
	return 0;
}