[백준] 1874 스택수열

1~n 까지의 수를 스택에 넣을 때 push , pop 을 이용해 주어진 배열을 만들수 있는지 알아보는게 문제다

1부터 차례로 넣으므로

만약 스택이 비었거나 또는 top이 현재보는 수와 같지 않다면

현재보는 수 까지 스택에 넣으면 된다

근데 만약 이 때 넣는수가 n보다 커진다면 만들수 없는 배열이 된다!!

이것만 잘 처리해준다면 쉽게 풀 수 있다..!

소스코드

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
int n;
int arr[100010];
stack<int> st;
vector<char> ans;
 
int main() {
    int it = 1;
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) scanf(" %d", &arr[i]);
    for (int i = 0; i < n; i++) {
        if (st.empty() || st.top() != arr[i]) {
            while (true) {
                if (it > n) {
                    puts("NO"); return 0;
                }
                st.push(it++);
                ans.push_back('+');
                if (st.top() == arr[i]) {
                    st.pop();
                    ans.push_back('-'); break;
                }
            }
        }
        else if (st.top() == arr[i]) {
            st.pop(); ans.push_back('-');
        }
    }
    for (int i = 0; i < ans.size(); i++) printf("%c\n", ans[i]);
}