[Silver 2] 1874번 스택 수열

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

1874번: 스택 수열

 

이 문제는 문제에 나와있는대로 스택을 사용하는 문제이다.

또한 수열이라는 뜻은 수의 나열이다.

 

문제의 해결을 위해 먼저 N까지의 숫자를 배열에 집어 넣는 방법을 먼저 떠올렸다.

하지만, 값을 받기 전 배열에 숫자를 넣게 된다면 뒤로 가는 연산을 수행하기 어렵다는 것을 알게 되었다.

 

따라서 먼저 값을 받고, 반복 중 스택에 숫자를 넣고, top을 넣은 숫자를 가리키도록 한다.

top이 가리키는 값이 찾는 값에 해당한다면 반복을 멈춘다.

 

반복에서 나와서 스택의 top이 찾고 싶은 값이라면 스택에서 제거하고 스택의 top을 한칸 내리는 연산을 수행한다.

 

마지막으로 스택의 top이 주어진 N보다 크게 된다면 NO를 출력하게 한다.

 

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

int main(){
    int N;
    cin>>N;
    vector<int> stack;
    int top = -1;
    int item = 1;
    vector<char> buffer;
    for(int i = 0;i<N;i++){
        int target;
        cin>>target;
        while(true){
            if(!stack.empty()){
                if(stack[top]==target){
                    break;
                }
            }
            buffer.push_back('+');
            stack.push_back(item);
            top +=1;
            item += 1;
            if(top>N){
                cout<<"NO"<<'\n';
                return 0;
            }
        }
        if(stack[top]==target) {
            buffer.push_back('-');
            stack.pop_back();
            top -= 1;
        }
    }
    for(int i =0;i<buffer.size();i++)
        cout<<buffer[i]<<'\n';
}