[BOJ / C++] 9935번 : 문자열 폭발

문제

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

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

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

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

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

입력

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

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

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

출력

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

Solved.ac 레벨

골드 IV

풀이

처음에는 문제 분류대로 스택을 활용한 정공법을 썼다. 예제 입출력은 만족했으나 왜인지 1%에서 틀렸다.

다른 방향으로 생각해서 문자열을 스택처럼 활용하기로 해봤다.

string target;
string bomb;
string ans;

 이렇게 세 문자열 변수를 사용했다. target은 탐색할 문자열, bomb은 폭탄 문자열, ans는 정답 문자열 및 스택으로 활용한 문자열이다.

먼저 target의 길이만큼 반복을 하며 ans에 한 글자씩 넣어준다.

ans의 맨 마지막 글자가 bomb 문자열의 마지막 글자와 동일할 때

- 현재까지의 ans의 길이가 bomb의 길이보다 작을 경우 폭탄 문자열로 날릴 수 있는 문자열이 없다.

- bomb을 뒤에서 앞으로 순회하며 ans의 마지막 글자와 비교한다.

    * bomb이 ans에 포함되어 있는 경우 예비 문자열 변수 tmp에 ans의 마지막 글자를 담은 후 ans를 pop_back() 하여 지운다.

    * bomb이 ans에 포함되어 있지 않은 경우 tmp를 뒤집어 다시 ans에 넣어 복구해준 뒤 탐색을 멈춘다. tmp를 다시 비워준다.

- target의 순회가 끝난 후 ans에 남아있는 문자가 없을 경우 FRULA를, 문자가 남아있을 경우 ans를 그대로 출력해준다.

Code

#include<bits/stdc++.h>

using namespace std;

string target;
string bomb;
string ans;

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

    cin >> target >> bomb;

    for(char i : target) {
        ans += i;
        //ans에 target을 한 글자씩 집어넣는다.

        if(ans.back() == bomb.back()) {
        //ans와 bomb의 마지막 글자가 같을 때
            if(ans.length() < bomb.length()) continue;
            //현재까지의 ans 길이가 bomb의 길이보다 작다면 지나간다.

            string tmp;
            for(int j = bomb.size() - 1; j >= 0; j--) {
                if(ans.back() != bomb[j]) {
                	//현재까지의 ans에 bomb이 포함되어있지 않다는게 확인되면
                    //역순으로 들어가있는 tmp를 뒤집어 ans를 복구시킨뒤
                    //탐색을 종료한다.
                    reverse(tmp.begin(), tmp.end());
                    ans += tmp;
                    tmp = "";
                    break;
                } else {
                	//bomb의 문자가 계속해서 발견되면
                    //다음 글자가 발견되지 않을 때를 대비해 tmp에 ans의 마지막 글자를 담고
                    //ans의 마지막 글자를 지운다.
                    tmp += ans.back();
                    ans.pop_back();
                }
            }
        }
    }

    if(ans.empty()) {
        cout << "FRULA\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

9935번: 문자열 폭발