[백준][스택] 9935 문자열 폭발 c++구현

목차

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

9935번: 문자열 폭발

문제

 

문제 구현 시 주의점

문자 길이가 매우 길기 때문에 시간복잡고다 O(N^2) 나오게 되면 시간초과가 되므로 주의해야 한다.

하지만 비교 문자열의 크기는 36으로 매우 작으므로 스택을 통해 검사하면서 넣어 주게 되면

O(N)시간 복잡도를 가질 수 있다.

 

 

문제 풀이

1. 비교 문자열이 12ab라면 b인 끝 문자열과 같지 않다면 그냥 스택에 넣어준다.
2. 끝 문자열과 같다면 기존 스택에서 빼낸 후 대기 스택에 넣어 계속해서 a 2 1 순으로 문자가 맞는 지 검사해준다.
3. 문자가 모두 같다면 대기 스택을 비워준다.
4. 문자가 다른 것이 있다면 대기스택에서 다시 원래 스택으로 넣어준다.
5. 이런식으로 1~4의 과정을 반복한 뒤 스택에서 빼내고 거꾸로 출력하면 된다.

 

코드 구현

#include <iostream>
#include<stack>

#include<algorithm>



using namespace std;
stack<char> s;   //문자 저장용 스택
stack<char> wait;   //문자 임시 대기열
int main()
{
    string comp, stand, ans;
    int c_size = comp.size();
    int s_size = stand.size();
    cin >> stand;
    cin >> comp;
    for (int i = 0; i < s_size; i++) {
        if (stand[i] == comp[c_size - 1]) {   //끝 문자열 같으므로 문자열 대기열로 넣으며 검사
            for (int j = 1; j < c_size; j++) {
                if (s.empty())break;
                char top = s.top();
                if (top != comp[c_size - 1 - j])
                    break;
                s.pop();
                wait.push(top);
            }
            if (wait.size() == c_size - 1) {   //대기하던 것 다 비워줌
                while (!wait.empty()) {
                    wait.pop();
                }
            }
            else {      //대기하던 것 다시 넣고 들어갈 차례 넣어줌
                while (!wait.empty()) {
                    s.push(wait.top());
                    wait.pop();
               }
                s.push(stand[i]);
            }
        }
        else {    //끝 문자와 다를 경우에는 그냥 넣어줌
            s.push(stand[i]);
        }
         
    }
    
    while (!s.empty()) {   //스택에 있던 char 빼냄
        ans+= s.top();
        s.pop();
    }
    if (ans.size() == 0) {
        cout << "FRULA";
    }
    else {
        for (int i = ans.size() - 1; i >= 0; i--) {    // 스택으로 인해 거꾸로 출력 해야함
            cout << ans[i];
        }
    }
  
    return 0;
}