[백준 1874번] [스택] 스택 수열

이 문제 자체는 그렇게 어렵지 않으나, 문제의 설명이 조금은 난해하다.

요약하여 말하자면, 주어진 스택을 pop시켜서 나온 결과를 수열로 만드는 것이 가능한지를 물어보는 것이고 push할때는 이전에 push한 수보다는 무조건 큰 것만 가능하다.

 

즉, 따라서 이 문제에서 이전까지 push한 값이 무엇인지를 추가적으로 저장해주는 작업을 해야한다.

 

다만, 이 문제에서 조건으로 제시한 NO의 기준은 기존에 스택 값의 top값이 pop시켜서 나와야하는 수보다 더 큰 경우에 발생시켜주면 된다.

왜냐하면 문제의 설명에 따르면 pop을 시켜서 나온 결과들의 집합인데, 나와야하는 값이 스택의 top값보다 더 커버리면 무조건 현재 스택의 top값을 pop시켜야한다.

그러면 조건을 만족시키지 않는다.

 

해당하는 알고리즘을 활용하여 코드를 구현하면 다음과 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstdlib>

using namespace std;

int main(void){
    int n;
    cin >> n;
    vector<int> data_store;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        data_store.push_back(temp);
    } // Data store

    stack<int> stack_store;
    int count = 2; // 1은 무조건 집어넣으므로 그 다음은 무조건 2 
    int index = 0; // 참조할 data_store의 index 저장
    stack_store.push(1); // 처음 1은 input으로 무조건 넣고 시작
    vector <string> result_store;
    result_store.push_back("+");

    while(index < n){
        
        // stack안에 있는 것보다 해당 index에 있는 값이 더 작으면 push한다.
        
        if ((stack_store.size() == 0) || (stack_store.top() < data_store[index])){
            stack_store.push(count);
            result_store.push_back("+");
            count += 1;
        }

        // 만약, 제일 위에 있는 것보다 더 작은 것을 index 값으로 가지는 경우 무조건 그 값을 pop시켜야하므로 절대로 안된다.
        
        else if(stack_store.top() > data_store[index]){
            cout << "NO\n";
            return 0;
        }

        // 같으면 pop시켜 빼낸다.

        else if(stack_store.top() == data_store[index]){
            index += 1;
            stack_store.pop();
            result_store.push_back("-");
        }

        // 먼역애 제일 위에 있는 것보다 더 큰 값을 index 값으로 가지는 경우 무조건 pop시켜서 제일 위에 있는 값을 내린다.
        else{
            stack_store.pop();
            result_store.push_back("-");
        }
    }

    for(int i = 0; i < result_store.size(); i++){
        cout << result_store[i] << "\n";
    }

    return 0;
}