[BOJ] 문자열 폭발

rany·2020년 11월 1일
0

Baekjoon Online Judge

목록 보기
4/10
post-thumbnail

✔️ 문제

😎 소스 코드

#include <iostream>
#include <cstring>
#include <stack>
#include <vector>

using namespace std;

void solution(string input, string exp){
  stack<char> s;
  vector<char> v;
  string answer;
  
  for (int i = (int)input.length(); i >= 0; i--) {
    s.push(input[i-1]);
    if (s.size() >= exp.length()){ // s의 사이즈가 폭발 문자열의 길이와 같거나 커짐
      for (int j = 0; j < exp.length(); ++j) { // top부터 폭발 문자열 문자 하나씩 비교
        if (s.top() == exp[j]) { // 같을 경우
          v.push_back(s.top());
          s.pop();
        } else { // 다를 경우
          if (v.size() != 0) {
            while (!v.empty()) {
              s.push(v.back());
              v.pop_back();
            }
          } else {
            break;
          }
        }
      } // for
      v.clear();
    } // if
  } // for

  s.pop(); // char 뒤에 붙는 이상한 이스케이프 시퀀스 없앰
  
  if (s.empty()) {
    answer += "FRULA";
  } else {
    while (!s.empty()) {
      answer += s.top();
      s.pop();
    }
  }
  
  cout << answer << endl;
} // solution()

int main(){
  string input, explosion;
  cin >> input >> explosion;
  
  solution(input, explosion);
  
  return 0;
}

✊ 문제를 풀고 나서

문제 접근

  1. 스택 s에 역순으로 하나씩 push
  2. 스택 사이즈가 폭발 문자열(exp)의 길이와 같거나 클 경우 폭발 문자열의 길이만큼 for loop 시작
    2-1. 폭발 문자열의 첫 문자와 스택 top을 비교
    2-2. 비교해서 폭발 문자열과 완전히 같으면? 스택 top부터 exp 길이만큼 하나씩 pop. 이때 뒤의 문자도 폭발 문자열과 같다는 보장이 없기 때문에 벡터 v에 pop한걸 push
    2-3. 비교해서 다르면? 벡터v에 저장한 원소들을 맨 마지막 원소부터 다시 스택 s에 push
  3. 스택 s가 완전히 비었으면 answer은 FRULA.
    3-1. 스택에 뭔가 남아있으면 스택이 공백 상태일 때 까지 하나씩 빼주면서 answer에 더해준다.

개재밌다.
스택 문제 조진다 ㄱㄱ

profile
개발개발

0개의 댓글