문자열 폭발 (feat. 백준, 9935번)

문자열 폭발
https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <deque>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    string str1, str2;
    cin >> str1 >> str2;
    deque<char> ans;
    for(auto& ch : str1){
        ans.push_back(ch);
        if(ans.size() >= str2.size()){
            string str;
            for(register int i = 0; i < str2.size(); ++i)
                str.push_back(ans.back()), ans.pop_back();
            reverse(str.begin(), str.end());
            if(str != str2)
                for(auto& t : str)
                    ans.push_back(t);
        }
    }

    if(ans.empty())
        cout << "FRULA";
    else
        while(!ans.empty()){
            cout << ans.front();
            ans.pop_front();
        }
        cout << "\n";
    return 0;
}
// *&)*@*

 

1. 마지막으로 입력받은 문자열 기준으로 폭발 문자열과 비교를 진행합니다.
2. 입력받은 문자열의 첫번째가 아닌 뒤쪽부터 폭발 문자열의 길이만큼만 비교하기 때문에 동일한 O(n)이지만 비교 횟수 자체는 월등하게 적습니다.
3. 저는 deque를 사용했지만 stack을 사용하여도 무방합니다. LIFO 자료구조를 사용하면 됩니다.