BOJ 1874. 스택 수열

문제

코드

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

using namespace std;
int arr[100001];
int main(int argc, char const *argv[])
{
    cin.tie(NULL);
    ios::sync_with_stdio(0);
    int n, num;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    stack<int> st;
    vector<char> v;
    int idx = 0;
    for (int i = 1; i <= n; i++)
    {
        st.push(i);
        v.push_back('+');
        if (i == st.top())
        {
            while (st.top() == arr[idx])
            {
                st.pop();
                idx++;
                v.push_back('-');
                if (st.empty())
                    break;
            }
        }
    }
    if (st.empty())
        for (int i = 0; i < v.size(); i++)
        {
            cout << v[i] << "\n";
        }
    else
    {
        cout << "no" << '\n';
    }
    return 0;
}

• 스택에 순서대로 하나씩 넣고 이미 배열에 담긴 인덱스와 맨 위의 스택 값과 비교해 같으면 pop하는 방식.
• 스택이 모두 비었으면 출력하고, 비어있지 않다면 불가능한 수열이므로 NO를 출력한다.