백준_1874 : 스택수열 - C++

문제

---

문제 해석

- 1부터 주어진 수 까지 순서대로 스택에 들어갈 때 주어진 수열을 만들 수 있는지 확인 하는 문제이다.

- 예를 들어 3까지 넣는다 가정 할 때 2, 1, 3은 다음과 같이 만들 수 있다.

- 스택에 1, 2를 넣은 후 2번 빼면 2, 1 순서대로 나온다.

- 그 후 3을 스택에 넣었다 빼면 2, 1, 3 수열을 만 들 수 있다.

- 이때 push, pop 의 순서를 출력 하는 문제이다.

---

알고리즘

- 주어진 수열을 vector 등을 통해 저장 한다.

- 이후 1부터 주어진 수인 N 까지 수를 stack 에 넣으면서 다음 작업을 수행 해 준다.

  - 만약 이번에 stack 에 들어갈 수가 수열의 순서에 맞다면 pop 을 해 주고 stack 의 top 과 수열의 다음 순서를 비교하는 과정을 반복 한다.

  - 반복 중에 stack 이 비거나 수열의 순서와 stack 의 top 이 같지 않을 때 ( ex)위 그림중 우측에서 stack 의 top 이 1이지만 수열의 순서(1) 이 1이 아니라면 위 반복을 break 하고 다시 stack 에 수를 push 해 준다.

- 모든 과정이 끝났을 때 stack 이 비어 있지 않다면 해당 수열은 만들 수 없는 수열이기 때문에 "NO" 를 출력 해 준다.

- 만약 수열이 비었다면 위 과정에서 push, pop 을 하면서 저장 해 두었던 +, - 를 순서대로 출력 하면 된다.

---

코드

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

int N, vector_i = 0;
int input[100001];
vector<char> ans;
stack<int> st;

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> input[i];
    }

    for(int i = 1; i <= N; i++){
        st.push(i);
        ans.push_back('+');
        
        while(!st.empty()){
            if(st.top() == input[vector_i]){
                vector_i += 1;
                st.pop();
                ans.push_back('-');
            } else {
                break;
            }
        }
    }
    if(st.size() > 0){
        cout << "NO" << '\n';
    } else {
        for(int i = 0; i < ans.size(); i++){
            cout << ans[i] << '\n';
        }
    }
    return 0;
}