[백준] 9935 문자열 폭발 with C++

문제설명

---

입출력 예제

---

개념

　문제의 목표는 주어진 문자열에서 특정 '폭발' 문자열을 제외하고 출력하는 것이다. 이를 해결하기 위해 입력 문자열에서 특정 문자열을 식별하고 삭제하는 과정이 필요하다.

 

　이러한 과정은 문자열을 찾는 작업에서 O(n)의 시간 복잡도와 특정 문자열을 삭제한 후 남은 요소들을 이동시키는 작업에서 O(n)의 시간 복잡도를 갖게 된다. 따라서 두 연산을 합치면 전체 알고리즘의 최악의 경우 시간 복잡도가 O(n^2)이 되므로, 큰 입력에 대해 비효율적이라는 결론을 내릴 수 있다.

 

　이를 해결하는 가장 효과적인 방법은 스택을 사용하는 것이다. 폭발 문자열의 마지막 문자와 현재 입력받은 문자를 비교하여, 완전히 일치할 경우 해당 문자열을 제거하는 방식으로 진행하면 된다.

---

풀이(1) 스택 활용

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int main()
{
	string str, fire;
	stack<char> st;
	cin >> str >> fire;

　입력 문자열 str, 폭발 문자열 fire을 초기화한다.

 

	if (fire.size() == 1)
	{
		size_t found = str.find(fire);

		while (found != std::string::npos)
		{
			str.erase(str.begin() + found, str.begin() + found + fire.size());
			found = str.find(fire);
		}

		if (str.empty())
			cout << "FRULA";

		else
			cout << str;

		return 0;
	}

　내가 작성한 알고리즘에서는 폭발 문자열의 크기가 1일 때 처리가 원활하게 되지 않아, if문을 통해 따로 처리해 주었다. 이런 비효율적인 방법을 개선한 것은 후에 풀이(2)에서 다루도록 하겠다.

 

	else
	{
		for (int i = 0; i < str.size(); ++i)
		{
			if (!st.empty() && str[i] == fire[fire.size() - 1])
			{
				stack<char> tmp;
				tmp.push(str[i]);

				for (int j = fire.size() - 1; j > 0; --j)
				{
					if (!st.empty() && st.top() == fire[j - 1])
					{
						tmp.push(st.top());
						st.pop();
					}

					else
					{
						while (!tmp.empty())
						{
							st.push(tmp.top());
							tmp.pop();
						}
					}
				}
			}

			else
				st.push(str[i]);
		}
	}

　폭발 문자열의 마지막 인덱스와 현재 문자가 같다면, 두 문자열을 비교하여 일치하는 경우엔 삭제를 한다. 만약 아닌 경우라면 다시 스택에 푸시해 준다.

 

	if (st.empty())
		cout << "FRULA";

	else
	{
		stack<char> ans;
		while (!st.empty())
		{
			ans.push(st.top());
			st.pop();
		}

		while (!ans.empty())
		{
			cout << ans.top();
			ans.pop();
		}
	}
}

　스택이 비어있으면 "FRULA" 문자열을 출력하고, 아닌 경우에 스택에 있는 문자를 꺼낸다.

 

총합본

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int main()
{
	string str, fire;
	stack<char> st;
	cin >> str >> fire;

	if (fire.size() == 1)
	{
		size_t found = str.find(fire);

		while (found != std::string::npos)
		{
			str.erase(str.begin() + found, str.begin() + found + fire.size());
			found = str.find(fire);
		}

		if (str.empty())
			cout << "FRULA";

		else
			cout << str;

		return 0;
	}

	else
	{
		for (int i = 0; i < str.size(); ++i)
		{
			if (!st.empty() && str[i] == fire[fire.size() - 1])
			{
				stack<char> tmp;
				tmp.push(str[i]);

				for (int j = fire.size() - 1; j > 0; --j)
				{
					if (!st.empty() && st.top() == fire[j - 1])
					{
						tmp.push(st.top());
						st.pop();
					}

					else
					{
						while (!tmp.empty())
						{
							st.push(tmp.top());
							tmp.pop();
						}
					}
				}
			}

			else
				st.push(str[i]);
		}
	}

	if (st.empty())
		cout << "FRULA";

	else
	{
		stack<char> ans;
		while (!st.empty())
		{
			ans.push(st.top());
			st.pop();
		}

		while (!ans.empty())
		{
			cout << ans.top();
			ans.pop();
		}
	}
}

---

풀이(2) 문자열 활용

#include <iostream>
using namespace std;

int main()
{
	string str, fire, res;
	cin >> str >> fire;

	for (const auto& ch : str)
	{
		res += ch;

		if (res.size() >= fire.size() && res.substr(res.size() - fire.size(), fire.size()) == fire)
			res.erase(res.end() - fire.size(), res.end());
	}

	if (res.empty())
		cout << "FRULA";
	else
		cout << res;
}

　문자열 res의 마지막 부분이 폭발 부분 문자열 fire과 일치하는지 확인하는 로직을 아주 간단하게 구현하였다. 여기서 문자열 res의 끝에서 폭발 문자열 fire의 길이만큼 뒤로 간 위치에서 fire의 길이만큼 잘라서, 이 부분이 fire과 일치한다면 지워주는 방식으로 하였다.