[백준 9935번] 문자열 폭팔

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

문자열 폭발 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초 (언어별 추가 시간 없음)	128 MB	10559	1699	1149	18.858%

문제

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1 

mirkovC4nizCC44
C4

예제 출력 1 

mirkovniz

알고리즘 스터디에서 스택 문제를 찾다가 발견한 문제이다. 그래서 처음에는 스택으로 해결했는데 C++로 해결한 사람 중에 수행 시간과 메모리가

꼴등이 나왔다. 뭔가 이상하다고 생각해서 문자열로 다시 풀었더니 정상적인 풀이 시간이 나왔다.

1. 문자열

#include<iostream>
#include<string>
using namespace std;
 
string str, ex, result, temp;
int size_s, size_e, index;
bool flag;
 
int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    str.reserve(1000001);
    ex.reserve(37);
    
    cin >> str >> ex;
 
    size_s = str.size();
    size_e = ex.size();
 
    for (int i = 0; i < size_s; i++) {
 
        result += str[i];
        index++;
        
        if (result[index - 1] == ex[size_e - 1] && result.size() >= size_e) {
            flag = true;
            for (int j = 0; j < size_e - 1; j++) {
                if (result[index - size_e + j] != ex[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                index = index - size_e;
                result.erase(index, size_e);
            }
        }
    }
 
    if (result.size() == 0) {
        cout << "FRULA";
    }
    else {
        cout << result;
    }
}

2. 스택

#include<iostream>
#include<stack>
#include<string>
 
using namespace std;
 
string str,ex, cpy, te_str;
char t1,t2;
int cnt;
bool flag;
unsigned long size;
stack<char> s1,s2;
 
int main(){
 
    cin >> str >> ex;
 
    size = ex.size();
 
    for(int i=0;i<str.size();i++) s1.push(str[i]);
 
    while(!s1.empty()){
        t1 = s1.top();
        s1.pop();
 
        if(ex[size - 1 - cnt] == t1){
            cnt++;
        }
        else{
            cnt = 0;
 
            if(ex[size - 1 - cnt] == t1){
                cnt++;
            }
        }
 
 
        s2.push(t1);
 
        if(cnt == size){ //폭발시켜야됨
            for(int i=0;i<size;i++) s2.pop();
 
            flag = true;
            while(flag){
                flag = false;
            for(int j=1;j<size;j++){
                if(s1.size() < j) continue;
                else if(s2.size() < size-j) continue;
                cpy = "";
 
                for(int i=0;i<j;i++){
                    te_str = s1.top();
                    s1.pop();
                    cpy.insert(0,te_str);
                }
 
                for(int i=0;i<size-j;i++){
                    te_str = s2.top();
                    s2.pop();
                    cpy.insert(cpy.size(),te_str);
                }
 
                if(cpy == ex){
                    flag = true;
                    break;
                }
                else{
                    for(int i=0;i<j;i++){
                        s1.push(cpy[i]);
                    }
                    for(int i=0;i<size-j;i++){
                        s2.push(cpy[size-1-i]);
                    }
                }
            }
            }
            cnt = 0;
        }
    }
 
    if(s2.empty()){
        cout << "FRULA";
    }
 
    else{
        while(!s2.empty()){
            cout << s2.top();
            s2.pop();
        }
    }
 
    return 0;
}