[Baekjoon/C++] 9935번 - 문자열 폭발

[백준] Baekjoon Online Judge

문제로 이동

 

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

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

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

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

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

 

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

 

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

 

---

풀이

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

stack<char> sk;
stack<char> result;

void move(stack<char>& a, stack<char>& b);

// a의 원소를 b로 모두 옮기는 함수
void move(stack<char>& a, stack<char>& b) {
    while (!a.empty()) {
        b.push(a.top());
        a.pop();
    }
}

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

    string s, bomb;
    cin >> s >> bomb;

    reverse(bomb.begin(), bomb.end()); // 폭발 문자열 뒤집기

    for (char c : s) {
        sk.push(c);

        if (c != bomb[0] || sk.size() < bomb.length()) continue;

        stack<char> save;

        // 폭발 문자열이 포함되어 있는지 확인하기
        for (char b : bomb) {
            if (sk.top() == b) {
                save.push(sk.top());
                sk.pop();
            }
            else {
                move(save, sk);
                break;
            }
        }
    }

    move(sk, result);

    // 출력
    if (result.empty()) cout << "FRULA\n";

    while (!result.empty()) {
        cout << result.top();
        result.pop();
    }

    return 0;
}

 

// a의 원소를 b로 모두 옮기는 함수
void move(stack<char>& a, stack<char>& b) {
    while (!a.empty()) {
        b.push(a.top());
        a.pop();
    }
}

 스택 a의 원소를 스택 b로 모두 옮기는 함수이다.

 

    reverse(bomb.begin(), bomb.end()); // 폭발 문자열 뒤집기

    for (char c : s) {
        sk.push(c);

        if (c != bomb[0] || sk.size() < bomb.length()) continue;

        stack<char> save;

        // 폭발 문자열이 포함되어 있는지 확인하기
        for (char b : bomb) {
            if (sk.top() == b) {
                save.push(sk.top());
                sk.pop();
            }
            else {
                move(save, sk);
                break;
            }
        }
    }

 폭발 문자열에 관한 코드를 작성할 때의 편의성을 위해 reverse함수로 bomb를 뒤집었다.

 주어진 문자열의 문자c를 sk에 넣다가 c가 폭발 문자열의 마지막 글자이고, sk의 원소의 수가 bomb보다 크다면 폭발 문자열이 포함되어 있는지 확인하게 된다. 폭발 문자열에 포함된 문자 순으로 sk에 문자가 들어가 있다면 pop연산을 한다. 이때, 폭발 문자열이 아닌 경우를 대비해 save에 pop을 한 문자를 저장하여야 한다.

 만약 폭발 문자열이 아니라면 save에 저장한 문자를 sk에 다시 넣어서 복구한다.