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

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

1874번: 스택 수열

 본 문제는 stack을 잘 사용할 수 있는지 물어보는 문제다. 예를 들어 stack이 empty인데 stack top, pop을 하는 경우를 생각해야 한다. 그것만 잘 고려한다면 쉽게 문제를 풀 수 있다. 그래서 그냥 모든 경우에 stack이 empty가 아닐 경우를 추가했다. 그 외 문제들은 스택 수열 FAQ를 참고하길 바란다. 입력의 개수가 100,000이므로 O(n)으로 문제를 풀어야 한다.

1. 입력된 숫자보다 stack top의 숫자가 작을 경우 push
2. 같으면 pop
3. stack top이 입력된 숫자보다 클 경우 NO
4. ※ stack empty를 주의할 것

#include <cstdio>
#include <stack>
#include <vector>
 
using namespace std;
 
int main() {
    int t, index = 1;
    scanf("%d", &t);
    stack<int> st;
    vector<char> v;
    while (t--) {
        int num;
        scanf("%d", &num);
        if (st.empty()) {
            st.push(index);
            index += 1;
            v.push_back('+');
        }
        if (!st.empty() && st.top() > num) {
            printf("NO");
            return 0;
        }
        while (!st.empty() && st.top() < num) {
            st.push(index);
            index += 1;
            v.push_back('+');
        }
        if (!st.empty() && st.top() == num) {
            st.pop();
            v.push_back('-');
        }
    }
    for (int i = 0; i < v.size(); i++) {
        printf("%c\n", v[i]);
    }
    return 0;
}