실패를 두려워하지 않고
될 때까지 덤비는 🔥
그런 프로그래머 😎

문제
풀이

💡Idea

문제를 보면, 괄호 쌍을 찾는 문제와 비슷한 느낌이 들고, 스택의 동작 방식을 사용하면 좋을 것 같은 느낌이 든다.
정답 문자열을 모을 때의 편의를 위해, 스택을 안 쓰고 그냥 vector를 쓰기로 했다.
(answer.insert(answer.end(), S.begin(), S.end());식의 복사를 하기 위해.)

input 문자열을 하나씩 읽으며 다음과 같은 과정을 수행한다.
참고로 스택에는 폭발 문자열에 포함된 문자들만 들어가게 된다.
스택에 폭발 가능한 문자열들을 넣다가, 폭발 문자열이 모두 모이면 터뜨려 없애주고, 폭발이 확실히 안된다면 정답 문자열에 넣어주는 방식이다.

  1. 폭발 문자열의 시작 문자면, 일단 스택에 집어 넣는다.
    • 뒤의 문자열에 따라 폭발할 수 있기 때문.
  2. 스택의 top에 이어지는 폭발 문자라면 스택에 집어 넣는다.
    • 뒤의 문자열에 따라 폭발할 수 있기 때문.
      1. 만약 폭발 문자열의 마지막 문자라면, 해당 폭발 문자열을 스택에서 제거 한다.
  3. 그 외의 문자들이 나온 경우, 스택에 있던 모든 문자열을 정답 문자열에 push하고 지운다.
  4. 모든 input 문자열을 순회하고, 남은 stack에 있는 문자열들은 모두 정답 문자열에 push한다.
Bomb!

🔑Code

/*
[문자열 폭발] 
- date: 25.09.29
*/
#include <bits/stdc++.h>
using namespace std;

string input_str;
string bomb_str;
unordered_map<char,char> nxt;
vector<char> S;
vector<char> answer;

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> input_str;
    cin >> bomb_str;

    int n = bomb_str.length()-1;
    char first_of_bomb = bomb_str[0];
    char last_of_bomb = bomb_str[n];

    // 폭발 문자열이 하나의 문자일 때
    if(first_of_bomb == last_of_bomb){
        input_str.erase(remove(input_str.begin(), input_str.end(), first_of_bomb), input_str.end());

        cout << ((input_str.length() == 0) ? "FRULA" : input_str);
        return 0;
    }

    for(int i = 0; i < n; i++){
        nxt[bomb_str[i]] = bomb_str[i+1];
    }

    for(char& c : input_str){
        if(c == first_of_bomb){
            S.emplace_back(c);
        } else if(!S.empty() && c == nxt[S.back()]){
            if(c == last_of_bomb)
                S.erase(S.end() - n, S.end());
            else
                S.emplace_back(c);
        } else{
            if(!S.empty()){
                answer.insert(answer.end(), S.begin(), S.end());
                S.clear();
            }
            answer.push_back(c);
        }
    }

    // 터지지 않고 남은 문자열 처리
    if(!S.empty()){
        answer.insert(answer.end(), S.begin(), S.end());
    }

    if(answer.empty())
        cout << "FRULA";
    else{
        for(char& c : answer){
            cout << c;
        }
    }

    return 0;
}

🗨️ Side Notes

원소 삭제

algorithm헤더에 있는 std::remove는 제거할 원소들을 제거하고, 컨테이너의 크기는 변경하지 않는다. 따라서 뒤쪽에는 쓰레기 값들이 남게 된다. 따라서 컨테이너의 멤버 함수 erase를 사용하여 쓰레기 값을 제거해줘야 한다. replace는 함수는 해당 자료구조의 새로운 끝을 가리키는 iterator를 반환하므로, 이를 이용해서 다음과 같이 코드를 작성할 수 있다.

v.erase(remove(v.begin(), v.end(), <지울 원소>), v.end());

참고