[BOJ/백준 1874][C++] 스택 수열

문제

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

백준 1874

백준 1874 입출력

 

문제 내용

스택에 1~n 숫자를 push와 pop을 할 수 있다.

단, 이때 반드시 오름차순으로 push를 해야만 한다.

우리는 입력으로 주어진 수열을 만들기 위해, 어떤 순서로 push와 pop을 하면 되는지를 구하면 된다.

push/pop을 통해 수열을 만들 수 없으면 "NO"를 출력하면 된다.

 

문제 풀이

백준 1874 풀이

예제 1을 순서대로 표시해 보았다.

스택의 가장 위에 있는 값보다 input의 값이 더 작으면 "NO"를 출력하고 끝내야 한다는 점을 주의하면 된다.

 

코드

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    stack<int> st;
    vector<char> result;

    int tmp;
    int usedMaxNumber = 0; // 이 변수를 통해 어떤 수까지 push했는지를 기억한다.
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        //비어있거나, st.top()이 입력보다 작아서 수를 입력할 수 있는 경우
        if (st.empty() || st.top() < tmp) { 
            for (int j = usedMaxNumber + 1; j <= tmp; j++) {
                st.push(j);
                result.push_back('+');
                usedMaxNumber = tmp;
            }
        } else if (st.top() > tmp) { //st.top()이 입력보다 더 크면 NO 출력
            cout << "NO";
            return 0;
        }

        if (st.top() == tmp) {
            st.pop();
            result.push_back('-');
        }
    }

    for (auto num : result)
        cout << num << '\n';
}