[백준 실버2] 1874 스택 수열

 

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

 

pop한 걸로 주어진 예제의 수열을 만들 수 있느냐가 관건이다.

 

1. 현재 수열 값 >= 자연수

현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며

자연수를 스택에 push한다.

그리고 push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다.

 

2. 현재 수열 값 < 자연수

혀재 수열의 값보다 자연스가 크다면 pop으로 스택에 있는 값을 꺼낸다.

꺼낸 값이 현재 수열 값이거나 아닐 수도 있다.

만약 아니라면 후입선출 원리에 따라 수열을 표현할 수 없으므로 no를 출력한 후 문제를 종료하고,

현재 수열 값이라면 그대로 조건문을 빠져나온다.

 

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

using namespace std;


int main(void)
{

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, num = 1;
    bool result = true;
    cin >> n;
    
    vector<int> arr(n, 0);
    vector<char> resultV;
    stack<int> stk;

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    for (int i = 0; i < n; i++)
    {
        int se = arr[i];
        if (se >= num) {
            while (se >= num)
            {
                stk.push(num++);
                resultV.push_back('+');
            }
            stk.pop();
            resultV.push_back('-');
        } else
        {
            int n2 = stk.top();
            stk.pop();
            if (n2 > se) {
                cout << "NO";
                result = false;
                break;
            } else {
                resultV.push_back('-');
            }
        }
    }
    if (result) {
        for (int i = 0; i < resultV.size(); i++) {
            cout << resultV[i] << '\n';
        }
    }
    return 0;
}