백준 1874 (스택 수열) / C++

문제 링크 : https://www.acmicpc.net/problem/1874

1874번: 스택 수열

>풀이

 

스택을 활용하는 간단한 문제였습니다.

 

스택에 들어가는 수가 오름차순 이라는 것만 기억하신다면 쉽게 풀 수 있을겁니다 :)

 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int main() {
    int N, num, idx = 0;			//idx 는 st_input을 위한 인덱스
    stack<int> st;
    vector<int> input, st_input;	//st_input 은 스택에 들어가는 수 (오름차순)
    vector<char> output;			//'-'와 '+'를 출력하기 위한 벡터

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &num);
        input.push_back(num);
        st_input.push_back(i + 1);
    }
    st_input.push_back(-1);
    
    for (int i = 0; i < input[0]; i++) {
        st.push(st_input[idx++]);
        output.push_back('+');
    }

    st.pop();
    output.push_back('-');

    for (int i = 1; i < N; i++) {
        if (st.empty()) {
            st.push(st_input[idx++]);
            output.push_back('+');
        }

        if (input[i] == st.top()) {
            st.pop();
            output.push_back('-');
        }
        else if (input[i] > st.top()) {
            while (st_input[idx] <= input[i]) {
                st.push(st_input[idx++]);
                output.push_back('+');

                if (idx >= N) break;
            }

            st.pop();
            output.push_back('-');
        }
        else {
            printf("NO");
            return 0;
        }
    }
    for (auto c : output)
        printf("%c\n", c);

    return 0;
}

(개발 환경 : vs code)