boj-9935 문자열 폭발

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

문제 소개

문자열과 폭발 문자열이 주어졌을 때, 모든 폭발이 끝난 후 남는 문자열을 구한다.

폭발을 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

문제 풀이

스택을 이용하여 풀이하였다. 다만 인덱스를 통한 접근이 필요하여 deque를 사용하였다.

입력받는 문자열과 폭발 문자열은 각각 변수 str과 target에 입력받았다.

반복문을 통해 str의 문자를 하나씩 deque에 넣으며 확인한다.

변수 idx의 초기값은 0 이며, 현재 문자와 target의 idx번째 문자가 동일하다면 1 증가하며, 그렇지 않다면 다시 0이 된다.

idx가 target.size()와 동일하다면 폭발 문자열을 발견한 것이므로 target.size()만큼 pop하여 deque에서 제거한다.

그리고 위 과정을 통해 폭발한 문자열의 좌우가 만나 새로운 폭발 문자열이 나타날 수 있으므로, 만약 현재 문자가 target의 마지막 문자와 같다면 인덱스를 거꾸로 거슬러 올라가며 폭발 문자열인지 확인한다. 폭발 문자열이 발견되었다면 deque에서 제거한다.

반복문이 끝난 후 결과로 deque가 비어있다면 FRULA를, 아니라면 남은 문자열을 출력한다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <deque>

int main() {
	using namespace std;
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string str, target;
	cin >> str >> target;

    // 폭발 문자열의 길이
	int target_size = target.size();

	deque<char> dq;
	int idx = 0;        // target의 해당 인덱스를 확인하게 됨

    // 문자열의 문자를 하나씩 입력받으며 확인
	for (int i = 0; i < str.size(); i++) {
		dq.push_back(str[i]);
		if (str[i] == target[idx]) {
			idx++;
		}
        // 이번 문자가 target의 마지막 문자라면
        // 혹시 문자열 폭발로 인해 새로운 폭발 문자열이 생겨났는지 확인
		else if (str[i] == target.back() && dq.size() >= target_size) {
			bool valid = true;
			for (int i = 0; i < target_size; i++) {
				if (target[target_size - 1 - i] != dq[dq.size() - 1 - i]) {
					valid = false;
					break;
				}
			}

			if (valid) {
				for (int i = 0; i < target_size; i++) {
					dq.pop_back();
				}
			}
			idx = 0;        // 폭발 문자열 존재 여부와 관계없이 idx를 0으로 변경
		}
        // 이외의 경우 idx를 0으로 변경
		else {
			idx = 0;
			if (str[i] == target[idx]) {    // 다만 이번 문자가 target의 첫 문자라면 idx++
				idx++;
			}
		}

        // 폭발 문자열을 발견했다면
		if (idx == target_size) {
			for (int i = 0; i < target_size; i++) {
				dq.pop_back();
			}
			idx = 0;
		}
	}

    // 결과 출력
	if (dq.empty()) {
		cout << "FRULA" << '\n';
	}
	else {
		for (char& t : dq) {
			cout << t;
		}
		cout << '\n';
	}

	return 0;
}