백준 9935번 문자열 폭발 ( C++ )

문제

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

 

해설

괄호문제에서 조건이 추가된 문제로 해석하면 된다.

stack을 사용하여 가장 상단의 값을 빼와 만족할때만 pop()하도록 설정

 

코드

#include <iostream>
#include <algorithm>
#include <stack>
 
using namespace std;
 
string line, boom, ret;
stack<pair<char, int>> s;
int boom_len;
 
void go(char a)
{
  if (s.empty() || s.top().second == 0)
  {
    if (boom[0] == a)
    {
      if (boom_len == 1)
        return;
      s.push({a, 1});
    }
    else
      s.push({a, 0});
    return;
  }
 
  int boom_cnt = s.top().second;
  if (boom[boom_cnt] == a)
  {
    boom_cnt++;
    s.push({a, boom_cnt});
  }
  else if (boom[0] == a)
  {
    s.push({a, 1});
  }
  else
  {
    s.push({a, 0});
  }
  if (boom_cnt == boom_len)
  {
    for (int i = 0; i < boom_len; i++)
      s.pop();
    return;
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> line;
  cin >> boom;
  boom_len = boom.length();
  for (char a : line)
  {
    go(a);
  }
 
  int s_len = s.size();
  for (int i = 0; i < s_len; i++)
  {
    ret += s.top().first;
    s.pop();
  }
  if (ret == "")
  {
    cout << "FRULA";
    return 0;
  }
 
  reverse(ret.begin(), ret.end());
  cout << ret;
  return 0;
}