[백준/C,C++] 1874번: 스택 수열

www.acmicpc.net/problem/1874

1874번: 스택 수열

1씩 증가하는 자연수를 푸쉬할 수 있는 스택으로 주어진 수열을 만들 수 있는가에 대한 문제입니다. 예제로 주어진 4, 3, 6, 8, 7, 5, 2, 1의 경우 1, 2, 3, 4를 차례로 push하고 pop을 2번 하면 4, 3이 출력됩니다. 이후 5, 6을 push하고 pop을 1번 하여 6을 출력, 7, 8을 push~.. 순으로 해당 수열을 만들어 낼 수 있습니다. 지금 순번에 맞는 자연수가 입력된 숫자보다 작으면 push후, '+'를 출력해주고, 입력된 숫자와 같다면 pop을 해주고, '-'를 출력해주면 됩니다. 저는 따로 결괏값 스택을 만들어 문자를 스택에 쌓아뒀다가 마지막에 출력하였습니다. 그 외 순번에 맞는 자연수가 입력된 숫자보다 클 경우 수열을 만들 수 없으므로 "NO"를 출력해주시면 됩니다. 예를 들어 수열이 4, 3, 4라면 4번을 push하고 2번을 pop하여 4, 3을 출력했지만 이제 순번에 맞는 자연수는 5이므로 4를 push할 수 없기 때문에 해당 수열은 만들 수 없습니다.

#include<iostream>
#include<vector>

using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; cin >> n;
    vector<int> stack(n);
    vector<char> res;
    int top = 0;
    bool chk = true;

    for (int i = 0; i < n; i++) {
        int num; cin >> num;
        while (top < num) {
            stack.push_back(++top);
            res.push_back('+');
        }
        if (stack.back() == num) {
            stack.pop_back();
            res.push_back('-');
        }
        else {
            chk = false;
        }
    }

    if (chk) {
        for (vector<char>::iterator it = res.begin(); it < res.end(); it++) {
            cout << *it << "\n";
        }
    }
    else {
        cout << "NO" << endl;
    }

    return 0;
}