[BOJ] 백준 9935 문자열 폭발

[BOJ] 백준 9935 문자열 폭발

문제 링크 : https://www.acmicpc.net/problem/9935


이 문제는 스택 자료구조를 사용하여 한 문자열에서 폭발문자열을 제거하는 문제입니다.
이 문제를 스택을 이용하지 않고, string 클래스에서 제공하는 함수들로만 해결하려 한다면
시간초과가 날 가능성이 높습니다.

문제해결방안 :

입력받은 문자열의 첫번째 항부터 순회를 시작합니다.
순회 도중 폭발문자열의 마지막 문자와 만나게 된다면, 폭발문자열의 마지막문자에서 첫번째 문자까지와 입력받은 문자열이 같다면 전부 POP(), 다르다면 PASS 하는 식 입니다.

소스코드 :

#include 
#include 
#include 
#include 
using namespace std;

int main() {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 // 문자열 s, 폭발문자열 c
 string s;   cin >> s;
 string c;   cin >> c;
 stack st;
 // 폭발 문자열의 길이 tsize
 int tsize = c.length();
 for (int i = 0; i < s.length(); i++) {
  st.push(s[i]);
  // st의 사이즈가 폭발문자열 길이보다 크거나 같을때.
  if (st.size() >= tsize) {
   int tmpsize = st.size();
   bool flag = false; // if c[q] != stack[] then true;
   string tmp = ""; // pop할 스택들을 임시로 저장해 둘 tmp 선언.
   for (int q = tsize - 1; q >= 0; q--) {
    // 스택의 top과 폭발문자가 같다면 st.pop()
    if (c[q] == st.top()) {
     tmp += st.top();  // top을 tmp에 임시저장.
     st.pop();
    }
    else {
     flag = true;
     break;
    }
   }
   // 폭발문자열과 st이 같다면, 임시 저장해 둔 tmp의 마지막 항부터 차례대로 push.
   if (flag) {
    for (int i = tmp.size() - 1; i >= 0; i--)st.push(tmp[i]);
   }
  }
 }
 int sizest = st.size();
 if (sizest == 0) cout << "FRULA" << endl;
 else {
  vector v;
  for (int i = 0; i < sizest; i++) {
   v.push_back(st.top());
   st.pop();
  }
  for (int i = sizest - 1; i >= 0; i--) {
   cout << v[i];
  }
 }
}