백준 9935 문자열 폭발 혼내주기

 

 

 

문자로 char형 double linked list를 만든 후 폭발 문자열을 발견하면 해당 폭발 문자열을 지우고, 폭발 문자열의 크기만큼 뒤로 돌아가서 다시 탐색한다.

다른 사람들의 풀이를 보니 비슷한 로직을 배열로 구현하면 더 빠르던데, 무지성 가장 빠른 코드로 다시 풀기가 오히려 접근법을 제한하는 것 같아 앞으로는 선택적으로 익히거나 참고만 하려고 한다.

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

list<char> l;
string s, bomb;

void input() {
    fastio;
    cin >> s >> bomb;
}

int main() {
    input();

    for(char c : s) {
        l.push_back(c);
    }

    for(auto it = l.begin(); it != l.end();) {
        // match?
        bool match = true;
        auto itt = it;
        for(int i = 0; i < bomb.size(); ++i, ++itt) {
            if(bomb[i] != *itt) {
                match = false;
                break;
            }
        }

        if(match) {
            it = l.erase(it, itt);
            // back by size of bomb
            for(int i = 0; i < bomb.size() && it != l.begin(); ++i, --it) { }
        }
        else {
            ++it;
        }
    }

    if(l.empty()) cout << "FRULA";
    else {
        for(auto it = l.begin(); it != l.end(); ++it) {
            cout << *it;
        }
    }
}