[BOJ/C++] 문자열 폭발

🥇 Gold 4

✏️ 1차 솔루션

⭐️ 문자열

1. 주어진 문자열을 돌면서 현재 문자가 폭발 문자열의 시작 문자라면 현재 문자부터 폭발 문자 길이의 문자열이 폭발 문자열과 같으면 이를 지움
2. 이어 붙인 문자열이 폭발 문자열이 될 수 있기 때문에 문자열을 지우고 난 후에는 처음부터 탐색

🚨 trouble

시간초과. String 문제에서 substr 과 erase 는 웬만하면 안 쓰는 게 좋을 것 같기는 함
Stack을 적극 활용할 것

✏️ 최종 솔루션

1. 문자열을 answer 문자열에 추가하면서 현재 문자가 폭발 문자열의 마지막 문자와 같으면 answer의 이전 문자들도 모두 폭발 문자열이 같은지 확인
2. 현재 문자가 폭발 문자와 같으면 answer 마지막 문자 pop 해주고 같은 문자는 저장해두기
3. 현재 문자가 폭발 문자와 같지 않으면 현재까지 pop 해줬던 문자를 reverse 해주고 다시 answer 에 저장하기

📌 self feedback

1. 문자열이 같은 부분을 확인할 때 첫번째 문자가 아닌 마지막 문자부터 탐색하는 것이 관건
2. 문자열을 stack 으로 활용한 것이 관건

✏️ 최종 code

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string s,b;
    cin >> s;
    cin >> b;
    
    string ans="";

    for(int i=0;i<s.size();i++) {
        ans+=s[i];
        if(ans.back()==b.back() && ans.size()>=b.size()) {
            string str="";
            for(int j=b.size()-1;j>=0;j--) {
                if(ans.back()==b[j]) {
                    ans.pop_back();
                    str+=b[j];
                }
                else {
                    reverse(str.begin(), str.end());
                    ans+=str;
                    break;
                }
            }
        }
    }
    
    if(ans.empty()) cout << "FRULA";
    else cout << ans;
}