[Baekjoon,1874]스택 수열

주어진 문제처럼 숫자를 1에서 부터 n까지 스택에 넣는데 이때 주어진 수열의 값이 나온 경우 pop해주면 된다. 만약 n까지의 수를 모두 연산한 후에 스택에 값이 남아있으면 수열을 만들 수 없기 때문에 빈 벡터를 반환하여 예외를 처리했다.

구현 시 스택에 -1을 먼저 넣음으로서 빈 스택의 top() 함수를 호출할 때 일어나는 버그를 잡아내었다. 그리고 입출력 값이 많아 scanf와 printf를 이용하였다.

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

const int MAX_N=100000;

int n,perm[MAX_N];

vector<char> getProcess()
{
    vector<char> ret;
    stack<int> st;
    int idx=0;
    st.push(-1);
    for(int i=1;i<=n;++i)
    {
        st.push(i);
        ret.push_back('+');
        while(idx<n && st.top()==perm[idx])
        {
            st.pop();
            ret.push_back('-');
            ++idx;
        }
    }
    // 스택으로 수열을 만들 수 없는 경우 
    if(st.top()!=-1)
        return vector<char>();
    
    return ret;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;++i)
        scanf("%d",&perm[i]);
    
    vector<char> ret=getProcess();
    
    if(ret.empty())
        cout<<"NO"<<endl;
    for(int i=0;i<ret.size();++i)
        printf("%c\n",ret[i]);
    
    return 0;
}