백준 9935 - 문자열 폭발(복습)

문제 링크입니다 https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

문제의 조건입니다. 입력 받은 문자열이 폭발 문자열을 포함한다면 해당 문자열이 사라집니다.

 

mirkovC4nizCC44 - 입력 받은 문자열

C4                    - 폭발 문자열 이라고 한다면

mirkovC4nizCC44는 폭발 문자열을 포함하고 있기에 

mirkovC4nizCC44 -> mirkovnizCC44 -> mirkovnizC4 -> mirkovniz 가 됩니다.

 

시간 제한이 2초지만 문자열의 길이가 최대 1,000,000이기에 2중 for문을 한다면 시간 초과가 됩니다.

따라서 스택 알고리즘을 사용해서 푸는 문제입니다.

 

제가 푼 방식은

1. 정답을 저장하는 문자열(A라고 하겠습니다)에 입력 받은 문자열의 문자들을 하나씩 저장합니다.

2. A에 저장된 문자가 폭발 문자열의 끝과 같은지 확인 합니다.

3. 문자가 같고, A의 길이가 폭발 문자열의 길이보다 길다면 폭발 문자열과 완전히 같은지 확인합니다.

4. 완전히 같다면 해당 문자열을 없애줍니다.

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>

using namespace std;

string arr, bomb;
char ans[1000001];
int idx;

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> arr >> bomb;
	for (int i = 0; i < arr.length(); i++) {
		ans[idx] = arr[i];
		idx++;
		if (ans[idx-1] == bomb[bomb.length() - 1]) {
			if (idx < bomb.length()) {
				continue;
			}
			bool find = true;
			for (int j = 0; j < bomb.length(); j++) {
				if (ans[idx - 1 - j] != bomb[bomb.length()-j-1]) {
					find = false;
					break;
				}
			}
			if (find) {
				idx = idx - bomb.length();
			}
		}
	}
	if (idx == 0) {
		cout << "FRULA";
	}
	else {
		for (int i = 0; i < idx; i++) {
			cout << ans[i];
		}
	}
	return 0;
}

 

질문, 조언 댓글 남겨주세요