백준 1874 - 스택 수열

문제

 

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

1874번: 스택 수열

 

 

풀이

 

수열을 확인하기 위해 스택을 이용해서 해결하는 문제이다. 스택은 top에 값만 확인할 수 있는 성질을 이용하면 문제를 해결할 수 있다. 만약 스택에 현재 입력된 숫자가 없다면 스택의 top이 현재 입력된 숫자까지 되도록 수들을 push한다. push 순서는 오름차순이므로 순서대로 숫자를 넣어주면 된다.

만약 현재 입력된 숫자가 스택에 존재한다면 현재 입력된 숫자는 스택의 top에 있어야 한다. 스택에서 pop한 순서대로 수열이 만들어지기 때문에 현재 입력된 숫자는 스택의 top에 존재해야 한다. 만약 그렇지 않다면 그 수열은 만들 수 없게 된다.

 

 

코드

 

#include <iostream>
#include <stack>
#include <vector>
 
using namespace std;
 
int n;
vector<char> sequence;
stack<int> st;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> n;
 
    int val;
    int i = 1;
 
    while(n--)
    {
        cin >> val;
        if (st.empty())
        {
            do
            {
                st.push(i++);
                sequence.push_back('+');
            } while (st.top() != val);
        }
 
        if (st.top() < val)
        {
            while (st.top() != val) 
            {
                st.push(i++);
                sequence.push_back('+');
            }
        } 
 
        if (st.top() == val)
        {
            st.pop();
            sequence.push_back('-');
        }
        else 
        {
            cout << "NO";
            return 0;
        }
    }
 
    for (int i=0; i<sequence.size(); i++) cout << sequence[i] << '\n';
 
    return 0;
}