[알고리즘] 백준 9935 문자열폭팔 // 폭팔은 스택, 끝문자만 비교하라

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

*풀이1

 

1. 입력 받기:
   - 문자열 s (원본 문자열)
   - 문자열 t (폭발 문자열)

2. 변수 초기화:
   - n = s의 길이
   - len = t의 길이
   - stk = 빈 스택 (문자 저장용)

3. 원본 문자열 s 순회:
   for i = 0부터 n-1까지:
      - 현재 문자 s[i]를 스택에 push
      - 만약 스택의 top이 s[i]와 같고, 스택 크기가 len 이상이면:
         - tmp = 빈 문자열 (임시 저장용)
         - for j = 0부터 len-1까지:
            - tmp에 스택의 top을 추가
            - 스택에서 pop
         - tmp를 뒤집음
         - 만약 tmp가 t와 다르면:
            - tmp의 모든 문자를 다시 스택에 push
         - (같으면 아무 작업도 하지 않음)

4. 결과 생성:
   - ret = 빈 문자열 (최종 결과 저장용)
   - while 스택이 비어있지 않으면:
      - ret에 스택의 top을 추가
      - 스택에서 pop
   - ret를 뒤집음

5. 결과 출력:
   - 만약 ret가 빈 문자열이면:
      - "FRULA" 출력
   - 아니면:
      - ret 출력

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s,t;
stack<char> stk;

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

   cin>>s>>t;

   int n = s.size();
   int len = t.size();

   for(int i=0;i<n;++i) {
      stk.push(s[i]);
      //stack의 top과 target의 끝이 같으면 검사시작
      if(stk.size() && stk.top()==s[i] && stk.size() >= len) {
         string tmp="";
         for(int j=0;j<len;++j) {
            tmp+=stk.top();
            stk.pop();
         }
         
         reverse(tmp.begin(),tmp.end());
         //원복
         if(tmp!=t) {
            for(int k=0;k<tmp.size();++k) {
               stk.push(tmp[k]);
            }
         }
         //같으면 원복을 안하면됨
      }
   }

   string ret="";
   while(stk.size()) {
      ret+=stk.top();
      stk.pop();
   }
   reverse(ret.begin(),ret.end());
   if(ret=="") {
      cout<<"FRULA";
   }
   else {
      cout<<ret;
   }

   return 0;
}

 

* 풀이2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s,t;
stack<char> stk;

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

   cin>>s>>t;
   int n = s.size();
   int len = t.size();
   
   string ret="";
   for(int i=0;i<n;++i) {
      ret+=s[i];
      if(len <= ret.size()) {
         string sub = ret.substr(ret.size()-len,ret.size()); //시작위치, 길이 (초과시 에러)
         if(sub==t) {
            ret.erase(ret.end()-len,ret.end()); //시작위치, 길이(초과시 전체삭제)
         }
      }
   }
   
   if(!ret.size())cout << "FRULA" << "\n";
   else cout << ret << "\n";
   return 0;
}