9935_문자열폭발

• 기본적으로 생각할 수 있는 방법

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

int main(void) {
	string inputString;
	string bombString;

	cin >> inputString;
	cin >> bombString;

	while (1) {
		int index = inputString.find(bombString);
		if (index == -1)break;

		inputString.erase(inputString.begin()+index, inputString.begin() + index + bombString.length());

	}
	if (inputString == "") cout << "FRULA" << endl;
	else cout << inputString << endl;
	return 0;
}

• 계속 번갈아 가면서 해당 부분 지우면서 반복하는 방법
  • 단, 현재 위와 같이 하는 경우 시간초과 걸림

스택을 이용한다.

• 스택에 넣는 것
  • 문자열의 인덱스, 폭발 문자열의 인덱스
• 현재 문자가 폭발 문자열의 첫 번째 문자와 같은 경우 스택에 넣기
• 다른 경우 스택이 비어있으면 넘어가고
• 다른 경우에 스택이 비어있지 않으면,
  • 스택의 가장 위에 있는 것 폭발 문자열의 인덱스를 가져옴 이것을 p라고 한경우
• 현재 문자 == 폭발 문자열 p+1문자와 같으면 스택 넣기
  • 이때 p+1이 폭발 문자열의 마지막 문자면 폭발 문자열 찾은것으로 지워야함
• 다르면, 스택을 모두 비움
• 폭발 문자열의 길이 1인 경우
  • 스택 사용 못함, 그래서 for문으로 체크

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include<algorithm>
using namespace std;
char a[1000001];
bool erased[1000001];
char b[100];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> a;
	cin >> b;
	int n = strlen(a);
	int m = strlen(b);

	if (m == 1) {
		for (int i = 0; i < n; i++) {
			if (a[i] == b[0]) {
				erased[i] = true;
			}
		}
	}
	else {
		stack<pair<int, int>> s;
		for (int i = 0; i < n; i++) {
			if (a[i] == b[0]) {
				s.push(make_pair(i, 0));
			}
			else {
				if (!s.empty()) {
					auto p = s.top();
					if (a[i] == b[p.second + 1]) {
						s.push(make_pair(i, p.second + 1));
						if (p.second + 1 == m - 1) {
							for (int k = 0; k < m; k++) {
								auto p = s.top();
								erased[p.first] = true;
								s.pop();
							}
						}
					}
					else {
						while (!s.empty()) {
							s.pop();
						}
					}
				}
			}
		}
	}
	bool printed = false;
	for (int i = 0; i < n; i++) {
		if (erased[i]) continue;
		cout << a[i];
		printed = true;
	}
	if (!printed) {
		cout << "FRULA" << '\\n';
	}

}

• 위와 같이 구현 하면됨,
• 이렇게 해야 제 시간안에 성공함