BOJ 9935] 문자열 폭발

[ 1차 시도 ]

- 스택에 담아서 끝에서 부터 검사하려고 했다.

- 이렇게 그렇게 하면 문장이 끝까지 일치하지 않으면 다시 처음부터 검사를 해야하는데

스택을 이용하면 처음부터 다시 검사를 할 수 없다는 것을 알게됨.

- 다른 방법을 모색하다 그냥 Array를 사용하면 될것 같다고 생각함.

 

[ 2차 시도 ]

- Vector를 이용해서 재도전

- 반복문을 통해 2개의 조건문을 동시에 해결하려다 out of range가 계속 떠서 그냥 차례대로 하기로함.

 

[ 원리 ]

1. 해결할 문자열과 Boom 문자열을 string 으로 입력받는다.

2. Boom의 길이만큼 벡터에 해결할 문자열을 vector에 push_back한다.

3. Boom의 길이 == vector의 size 이면,  vector == Boom 인지 검사한다.

4. 만약 vector와 Boom의 문자열이 다르면, +1한 vector의 문자부터 검사.

5. 위 과정을 반복

 

#include <iostream>
#include <stack>
#include <queue>

#include <vector>

using namespace std;


int main()
{
    string str;
    string key;
    vector<char> v;
    bool chk = false;

    cin >> str;
    cin >> key;
    
    int str_len = str.length();
    int key_len = key.length();
   
    for (int i=0; i < str_len; i++) {
        v.push_back(str[i]);

        if (v.size() >= key_len) {
            chk = false;
            for (int j = 0; j < key_len; j++) {
                if (key[j] != v[v.size() - key_len + j])
                    chk = true;
            }

            if (!chk) {
                for (int j = 0; j < key_len; j++) {
                    v.pop_back();
                }
            }
        }
    }
    
    if (v.empty()) {
        cout << "FRULA";
        return 0;
    }
    for (int i = 0; i < v.size(); i++) {
        cout << v[i];
    }
    
}