[백준 9935] 문자열 폭발

🔗알고리즘 문제

자료구조 수업시간에 해결한 문제, 나름 알고리즘을 많이 풀어보고 익숙하다고 생각하여 자신있게 도전하였고 생각보다 잘 풀 수 있어 기분이 좋았다 : )

문제 분석

이 문제는 문자열과 폭탄 문자열이 주어질 때 문자열에서 폭탄 문자열을 모두 제거하여 출력하는 문제이다.

이 때 폭탄 문자열을 제거하여서 새로운 폭탄 문자열이 생기는 경우에도 제거하여야 한다.

발상 및 알고리즘 설계

이 문제를 해결하기 위해서는 문자열 속 폭탄 문자열을 찾는 것이 가장 중요하다!

문자열의 앞에서부터 for문을 진행하며 하나하나 검사해주다가 폭탄 문자열의 끝 문자와 같은 부분을 발견하면 폭탄 문자열의 크기만큼 for문을 반대로 진행하며 하나씩 제거해주었다. 제거한 부분이 폭탄 문자열과 동일하다면 그대로 다시 진행해주었고 아니라면 다시 문자열에 추가해주었다.

코드

#include<iostream>
#include<deque>
#include<algorithm>

using namespace std;

int main(){
    deque<char> dq;

    string input;
    string target;

    cin >> input >> target;

    for(int i = 0; i < input.length(); i++){
        dq.push_back(input[i]);
        
        if(target.back() == input[i]){
            string temp = "";

            for(int j = target.length(); j > 0; j--){
                if(dq.empty() == false){
                    temp.push_back(dq.back());
                    dq.pop_back();
                }
            }

            reverse(temp.begin(), temp.end());

            if(temp != target){
                for(int j = 0; j < temp.length(); j++){
                    dq.push_back(temp[j]);
                }
            }
        }
    }

    if(dq.empty()){
        cout << "FRULA";
        return 0;
    }

    while(dq.empty() == false){
        cout << dq.front();
        dq.pop_front();
    }
}