백준 1874 - 스택 수열

문제 설명

크게 두가지 경우를 나눈다. 

1.stack이 빈 경우
2.stack이 비지 않은 경우 

1.1

stack에 오름차순의 수를 넣어주고 answer에 +를 추가한다. 

 

2.1

stack의 top == arr[index]

->stack pop

->answer에 -추가

 

2.2

stack의 top < arr[index]

->stack push

->answer에 +추가

 

2.3

stack의 top > arr[index]

불가, NO!!!!

 

*index를 언제 증가시킬지에 대해 고민하고 써야한다. 

*stack이 빈 경웨 top()을 사용하면 error가 발생한다. if문으로 stack이 비지 않은 경우에만 사용하여야 한다. 

 

#include <iostream>
#include <string>
#include <stack>
#include <vector>

using namespace std;

vector<string> answer;//array for +-
stack<int> st; // stack

int PushPop(vector<int> arr)
{
    int arrIndex = 0;
    int pushNumber = 1;
    while (arrIndex <= arr.size() - 1)
    {
        if (st.empty())
        {
            st.push(pushNumber++);
            answer.push_back("+");
        }
        else
        {
            if (st.top() == arr[arrIndex]) // 해당하는 값이 맨위에 있는 경우
            {
                st.pop();
                answer.push_back("-");
                arrIndex++;
            }
            else if (st.top() < arr[arrIndex])
            {
                st.push(pushNumber++);
                answer.push_back("+");
            }
            else // top > arr[arrIndex]
            {
                return 0;
            }
        }
    }
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> arr; //수열
    
    for (int i = 0; i < N; ++i)
    {
        int tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    
    if (PushPop(arr))
    {
        for (auto it = answer.begin(); it != answer.end(); it++)
        {
            cout << *it << '\n';
        }
    }
    else cout << "NO" << '\n';
    
    return 0;
}