[백준/C++] 문자열 폭발

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 문자열이 완성되면 삭제를 하고, 뒤에 문자들을 이어 붙이면 되는 문제다.

 

문제를 풀 때, 앞에서 부터 문자열을 추가해 나가다가 M의 마지막 문자가 나오면, 저장된 문자들을 탐색해 삭제가 되는지 확인했다.

 

아래 그림을 통해 자세하게 알아보자

M의 마지막 문자인 4가 나왔으므로 4부터 탐색해 문자열 M과 같은지 확인한다.

C4로 같았으므로 문자열을 삭제해 준다.

 

마찬가지로 진행을 하면 아래와 같이 정답이 나오게 된다.

이렇게 하면 문자열을 앞에서부터 n번 탐색해 문제를 해결할 수 있다. 

 

이때 문자를 저장하고 삭제를 하는 방법은 여러가지가 있겠지만, 뒤에 있는 문자부터 빼 사용할 것이므로 stack을 이용해 문제를 풀었다.

 

​

[아이디어 정리]

1. 앞에서부터 탐색을 하며 문자들을 stack에 추가한다.
2. 만약 들어온 문자가 M의 마지막 문자와 같다면, 삭제가 되는 문자인지 확인한다. (stack에 맨 위에 있는 문자들을 빼면서 확인)
3. 만약 삭제가 되는 문자라면 stack에서 제거하고, 삭제가 되지 않는 문자라면 stack에 그대로 남겨둔다.
4. 최종적으로 stack에 저장된 문자들을 꺼내 출력한다.

 

 

 

Code

 

 

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	string N, M;
	cin >> N>>M;stack<char> st;
	for (int i = 0; i < N.length(); i++)
	{
		st.push(N[i]);
		if (N[i] == M[M.length() - 1])
		{
			string temp="";
			bool isRemove = true;
			for (int j= M.length() - 1; j>= 0; j--)
			{
				if (!st.empty()&& M[j] == st.top())
				{
					temp += st.top();
					st.pop();
				}				
				else
				{
					isRemove = false;
					break;
				}
			}
			if (!isRemove)
			{
				for (int j = temp.length() - 1; j >= 0; j--) 
				{
					st.push(temp[j]);
				}
			}
		}
	}
	stack<char> tt;
	while (!st.empty())
	{
		tt.push(st.top());
		st.pop();
	}
	if (tt.empty())
	{
		cout << "FRULA";
	}
	else
	{
		while (!tt.empty())
		{
			cout<<tt.top();
			tt.pop();
		}
	}
	return 0;
}

 

---

처음에 시간초과가 났는데, 문자를 출력하는 부분에서 string을 이용했더니 복사가 계속 일어나서 시간이 초과가 난 것이었다.

혹시나 했는데 역시나...

9935번: 문자열 폭발