백준 9935번 c++ "문자열 폭발" -PlusUltraCode-

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

 

[필자 사고]

처음에 필자는 string 내장함수인 find 와 erase를 사용하여 문제를 해결했지만 시간초과가 발생했다.

찾아보니 erase의 시간복잡도가 최악일경우 O(n^2) 이 발생할 수도 있기 때문이다.

그래서 stack을 이용하여 폭파시킬 bomb 문자열이 들어가 있으면 스택에서 지우는 형식으로 방향을 바꿨다.

필자가 실수한 점은 string temp; 변수를 초기화 시키지 않고 계속 사용하여 메모리초과가 발생했다.

ㅇㅏ래는 소스코드 해설이다.

[코드 해설]

 

• 문자열 str과 폭발 문자열 bomb을 입력받는다.
  • 사용자로부터 문자열 str과 폭발 문자열 bomb을 입력받아, 이후 문자열 처리에 사용할 준비를 한다.
• 스택을 사용하여 문자열을 처리한다.
  • 문자열 str을 앞에서부터 한 글자씩 읽어가며 스택에 추가한다.
  • 스택의 최상단 문자가 폭발 문자열 bomb의 마지막 문자와 같고, 스택의 크기가 폭발 문자열의 길이 이상이라면 폭발 여부를 확인한다.
• 폭발 문자열 확인 및 제거
  • 스택에서 폭발 문자열의 길이만큼 문자를 꺼내 temp에 저장한다.
  • temp를 뒤집어 폭발 문자열과 비교한다.
    • 만약 temp가 폭발 문자열과 다르다면, temp의 모든 문자를 다시 스택에 넣는다.
    • 만약 같다면, 폭발 문자열이 제거되므로 아무 작업도 하지 않는다.
• 스택의 남은 문자로 결과 문자열 생성
  • 문자열 str의 모든 문자를 처리한 후, 스택에 남아 있는 문자를 하나씩 꺼내 결과 문자열 ans에 추가한다.
  • ans는 역순으로 생성되므로 최종적으로 뒤집어야 원래의 순서대로 출력할 수 있다.
• 결과 출력
  • 결과 문자열 ans가 비어 있다면 모든 문자가 제거된 것이므로 "FRULA"를 출력한다.
  • 그렇지 않다면 ans를 출력한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <algorithm>

using namespace std;

string str;
string bomb;
string temp="";
string ans="";
stack<char> myStack;

void Input() {
	cin >> str >> bomb;
}

void Game_Start() {

	ans.reserve(1000000);

	for (int i = 0; i < str.size(); i++) {
		char ch = str[i];
		myStack.push(ch);

		if (myStack.top() == bomb[bomb.size() - 1] && myStack.size() >= bomb.size()) {
			temp = "";
			for (int k = 0; k < bomb.size(); k++) {

				temp += myStack.top();
				myStack.pop();
			}

			reverse(temp.begin(), temp.end());
			if (temp != bomb) {
				for (int k = 0; k < temp.size(); k++) {
					myStack.push(temp[k]);
				}
			}
		}


	}

	while (!myStack.empty()) {
		ans.push_back(myStack.top());
		myStack.pop();
	}

	reverse(ans.begin(), ans.end());

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

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	Input();
	Game_Start();
}