[BOJ 1874] 스택 수열

문제 출처

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

 

문제 설명

스택 성질에 대해 이해가 필요한 문제입니다. 처음에 고민하다가 입력받은 숫자가 나올때까지 push하다가 입력받은 숫자가 나오면 pop해주면 쉽게 풀 수 있는 문제입니다. idea가 필요했던 문제!

 

소스 코드

//
//  main.cpp
//  BOJ_1874
//
//  Created by sw on 17/12/2019.
//  Copyright © 2019 seungwoo. All rights reserved.
//

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    int num[n];
    vector<char> ret;
    stack<int> st;
    
    for (int i=0; i<n; i++) cin>>num[i];
    
    int idx=0;
    for (int i=1; i<=n; i++) {
        st.push(i);
        ret.push_back('+');

        while (!st.empty() && st.top() == num[idx]) {
            idx++;
            st.pop();
            ret.push_back('-');
        }
    }
    
    if (!st.empty()) cout<<"NO"<<"\n";
    else for (auto c : ret) cout<<c<<"\n";
    
    return 0;
}