백준 9935번 : 문자열 폭발 - C++ 스택 직접 구현

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

9935번: 문자열 폭발

1.문제설명

 

INPUT

12ab112ab2ab
12ab

첫 째로 일반 문자열이 주어지고

두번째로 폭발하는 문자열이 주어진다.

1. 일반 문자열 내에 폭발 문자열이 있을 경우 폭발 문자열을 없애줘야한다.

2. 폭발 문자열을 없앤 결과 또 폭발문자열이 포함되어 있을 경우 다시 폭발문자열을 없애줘야한다.

 

1과 2를 문자열 내에 폭발문자열이 없을 때까지 반복한다.

 

 

 

---

2.접근방법[알고리즘]

백준 문자열 폭발

그동안 습관적으로 STL을 사용하던 버릇에 긴장감을 주는 문제다.

 

스택을 직접 구현해야 가장 편하게 풀 수 있다.

 

입력받은 첫째 문자열을 돌면서 stack에 char 문자 하나씩 넣어주다가

stack의 가장 위 문자가 폭발 문자열의 마지막 문자와 동일하면

그 문자가 폭발 문자열을 이루고 있는지 확인하고,

 

폭발문자열이 발견되면 그만큼 pop 해주어야한다.

pop 해주는 건 p 변수를 폭발문자열의 크기 만큼 빼주면 쉽게 구현할 수 있다.

 

 

---

3.문제풀이코드 C++

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

char stack[1000001];
int p = 0;
string str;
string bomb;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> str;
	cin >> bomb;
	
	for (int i = 0; i < str.length(); i++) {
		stack[p++] = str[i];

		if (p >= bomb.length() && stack[p - 1] == bomb[bomb.length() - 1]) {
			bool is_same = true;
			for (int j = 0; j < bomb.length(); j++) {
				if (bomb[j] != stack[p - bomb.length() + j]) {
					is_same = false;
				}
			}
			if (is_same) {
				p -= bomb.length();
			}
		}
	}

	if (p == 0) {
		cout << "FRULA" << '\n';
	}
	else {
		for (int i = 0; i < p; i++) {
			cout << stack[i];
		}
		cout << '\n';
	}


	return 0;
}

백준 9935번 : 문자열 폭발