(9935) 문자열 폭발

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

단계별로 풀어보기

38단계(스택, 큐, 덱 2) 1번째

 

 

 

당연히 정석은 스택을 사용해 한 글자씩 집어넣으며 폭발 문자열이 나오면 스택에서 꺼내는 방식이다.

하지만 그냥 string으로 푸는 테크닉을 찾아냈다.

 

 

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  string str, boom;
  stack<char> s;
  vector<char> v;

  cin >> str >> boom;
  int len= boom.length();

  if(len==1){
    for(int i=0;i<str.length();i++){
      if(str[i]!=boom[0]){
        s.push(str[i]);
      }
    }
  }else{
    for(int i=0;i<str.length();i++){
      s.push(str[i]);
  
      if(str[i]==boom[0]){
        v.push_back(1);
        continue;
      }else if(v.empty()){
        continue;
      }
  
      if(str[i]==boom[v.back()]){
        v.back()++;
  
        if(v.back()==len){
          v.pop_back();
          for(int j=0;j<len;j++){
            s.pop();
          }
        }
      }else{
        v= vector<char> ();
      }
    }
  }
  
  if(s.empty()){
    cout << "FRULA";
  }else{
    string ans= "";
    
    while(!s.empty()){
      ans= s.top()+ans;
      s.pop();
    }

    cout << ans;
  }
  
  return 0;
}

 

 

 

string의 substr은 문자열을 복사하므로 O(N)이 걸리지만, C++17부터 추가된 string_view 클래스를 이용하면 임시 객체를 생성하지 않고 string의 각종 함수를 쓸 수 있다. 또한 resize로 기존 문자열 길이보다 작게 재설정하면 O(1)로 문자열의 뒤쪽을 자르는 효과를 낼 수 있다.

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  string str, boom, s= "";
  
  cin >> str >> boom;
  
  for(char c:str){
    s+= c;
    
    if(s.length()>=boom.length()){
      if(string_view(s).substr(s.length()-boom.length())==boom){
        s.resize(s.length()-boom.length());
      }
    }
  }
  
  cout << (s=="" ? "FRULA" : s);
  
  return 0;
}