9935 문자열 폭팔

9935 문자열 폭팔

문자열을 입력받다가 특정 문자열이 감지되면

문자열을 터트린다

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

1. 문제

---

간단 설명

문자열과 폭팔 문자열을 입력받는다

폭팔 문자열이 문자열 내에 감지되면, 폭팔 문자열 내용을 날려버리고

남은 문자열은 합쳐진다

시간 초과에 주의할 것

2. 문제 분석

---

알고리즘

1. 베이스 문자열과 폭팔 문자열을 입력받는다
2. 베이스 문자열을 앞에서부터 차례로 스택에 집어넣기 시작한다. 
    다 집어넣었다면 반복문을 종료한다
3. 현재 넣고있는 문자가 폭팔 문자열의 끝 문자와 같고, 
    스택에 저장된 문자의 총 개수가, 폭팔 문자열보다 길다면,
    3-1. 폭팔 문자열의 개수만큼 문자열을 꺼낸다
    3-2. 이 문자열을 뒤집어서 폭팔 문자열과 비교한다
    3-3. 만약 같다면 폭팔해서 없어지므로 끝
    3-4. 같지 않다면, 꺼낸 문자열을 앞에서부터 차례로 다시 집어넣는다 
4. 베이스 문자열을 모두 넣었다면 결과 문자열에 스택의 위에서 부터 차례려 저장한다
5. 결과 문자열을 뒤집는다
    - 스택의 top에서부터 pop 했으므로 순서가 거꾸로 되어있음
6. 결과 문자열이 비었다면 "FRULA"를, 아니라면 결과 문자열 내용을 출력한다.

필요변수

• 베이스 문자열 string str, 폭팔 문자열 string bomb
• 스택을 이용해 문제 해결 stack<char> st
• 문자열을 뒤집을 때 사용하기 위한 algorithm 라이브러리의 reverse 함수

주의점

• 폭팔하고 남은 문자열이 또 폭팔할수도 있다
• 스택에서 pop 할 때, segfault에 주의할 것. 이미 empty인데 더 꺼내려고 할 경우 프로그램이 에러 발생함.
• 문자열을 꺼냈다가 집어넣을 때, 순서에 주의할것

3. 소스코드

---

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>

using namespace std;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	string str, bomb;
	cin >> str >> bomb;
	stack<char> st;

	for (auto ch : str) {
		st.push(ch);

		// 스택에 저장된 문자열의 길이가 폭탄보다 길고, 
		// 현재 추가된 글자가 폭탄의 마지막 글자와 같다면
		if (st.size() >= bomb.size() && ch == bomb[bomb.size() - 1]) {
			string tmp;
			// 폭탄의 문자열 개수 만큼 st에서 꺼냄
			for (int i = 0; i < bomb.size(); i++) {
				char ch = st.top();
				st.pop();
				tmp += ch;
			}
			reverse(tmp.begin(), tmp.end());

			// 꺼낸 문자열과 폭탄이 같으면 되돌려놓지 않음.
			// 같은 경우에만 다시 넣어줌
			if (tmp != bomb) {
				for (auto ch : tmp) {
					st.push(ch);
				}
			}

		}

	}

	string result;
	while (!st.empty()) {
		result += st.top();
		st.pop();
	}
	if (result == "") {
		cout << "FRULA";
	}
	else {
		reverse(result.begin(), result.end());
		cout << result;
	}
	
	
	return 0;
}

스택 이외에 여러문자를 한번에 삭제하거나, 치환하는 방법으로 해결할 수 도 있을듯하다

Python의 repalceAll같은 경우는 시간초과가 난다고 하지만, 실제 사용하게된다면 이쪽을 사용할듯

C++에서는 replace, regex_replace 등을 사용하면 될 것 같다

#include <iostream>
#include <string>
#include <regex>

using namespace std;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	string str, bomb;
	cin >> str >> bomb;

	while (1) {
		string before = str;

		str = regex_replace(str, regex(bomb), "");
		
		if (before == str) break;
	}
	
	if (str == "") {
		cout << "FRULA";
	}
	else {
		cout << str;
	}
	return 0;
}

시간초과가 나지만 이쪽이 더 가독성이 좋은듯