백준 09935 - 문자열 폭발

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

9935번: 문자열 폭발

 

고려사항

• deque 활용. stack 개념만 있으면 되지만 출력을 간편하게 하기 위해 dequeu 사용!
• kmp 알고리즘을 수정하여 failure function 을 정의하여 다음 문자열 탐색 idx를 target 길이만큼 뒤로 돌리기로도
  가능해보이나 생각보다 까다로워서 포기...(아직 kmp 알고리즘이 능숙하지 못한 내 탓..)
• 16 - 20 라인 참조, 먼저 target 문자열 길이 -1 만큼 문자를 dq에 넣어두고,
  ( dq.back()이 trigger (=target.back)과 같으면 tarLen 만큼 뽑으면서 비교하기 때문에, 최소 tarLen 만큼 문자가 담겨 있기 위해! )
  str[tarLen-1] 부터 dq에 옮기면서 탐색 시작!
• dq 에 넣은 그 문자가 trigger 와 같다면, tarLen 번 문자를 tmp 에 옮기면서 pop한다.
• 비교 도중 target 과 다름이 판명나면 break, tarLen 만큼 비교했는데 같다면 bomb = true 인 상태이다!
• tmp 를 초기화 해주며, bomb == false 이면 다시 dq에 옮겨준다.
  문자열이 일치해서 bomb == true 이면, dq에 옮길 필요없다! ( 폭발! )
• 다시 문자를 옮기고 반복!
• 모든 문자를 다 옮기고 검사가 끝났을 때, 조건에 맞게 출력!

 

#include <iostream>
#include <deque>
using namespace std;
 
int main(){
    string str, target, ans;
    cin>>str>>target;
 
    deque<char> dq;
    deque<char> tmp;
    char trigger = target.back();
    int strLen = str.length();
    int tarLen = target.length();
    bool bomb;
 
    for(int i=0;i<tarLen-1;++i){
        dq.push_back(str[i]);
    }
 
    for(int i=tarLen-1;i<strLen;++i){
        dq.push_back(str[i]);
        if(dq.back() == trigger){
            bomb = true;
            for(int j=0;j<tarLen;++j){
                if(dq.back() != target[tarLen-1-j]){
                    bomb = false;
                    break;
                }
                tmp.push_back(dq.back());
                dq.pop_back();
            }
 
            while(!tmp.empty()){
                if(!bomb){
                    dq.push_back(tmp.back());
                }
                tmp.pop_back();
            }
        }
    }
 
    if(dq.empty()){
        cout<<"FRULA";
    }else{
        while(!dq.empty()){
            cout<<dq.front();
            dq.pop_front();
        }
    }
 
    return 0;
}