[백준-9935] 문자열폭발

단순 탐색 문제인것 같다.

문자와 정수 pair 를 저장하는 vector 를 만든다. 그 후 문자열의 값을 하나씩 확인하면서 문자를 vector 에 넣되, 넣을 때 비교할 폭탄 문자열과 확인하여 같은 값이라면 몇번재 index 와 같은지를 정수로 같이 넣어준다.

이로써 폭탄이 만일 터지더라도 그 다음에 저장되어있는 정수를 확인해 계속해서 이어지는 문자가 들어올 시 폭탄이 터지도록 로직을 구현할 수 있다.

복잡도는 100만 * 36 + 36n? 정도? 라서 2초에 비해 넉넉한 복잡도를 가질 것이라 생각된다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <iostream>
#include <tuple>
#include <cmath>
#include <stack>

using namespace std;
typedef pair<char, int> pii;

int main()
{
    string a, b;
    vector<pii> st;

    cin >> a >> b;
    int cnt = 0;
    for (int i = 0; i < a.size(); i++) {
        if (st.empty() || st.back().second < 0) {
            st.push_back({ a.at(i), (b.at(0) == a.at(i) ? 0 : -1) });
        }
        else {
            if (st.back().second >= 0) {
                if (b.at(st.back().second + 1) == a.at(i)) 
                    st.push_back({ a.at(i), st.back().second + 1 });
                else 
                    st.push_back({ a.at(i), (b.at(0) == a.at(i) ? 0 : -1) });
            }
        }

        if (st.back().second == b.size() - 1) {
            for (int k = 0; k < b.size(); k++)  st.pop_back();
        }
    }
    if (st.empty()) cout << "FRULA\n";
    else {
        for (auto c : st) printf("%c", c);
    }
    

    return 0;
}

 

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

9935번: 문자열 폭발