[백준] 1874 스택 수열

문제 설명

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

1874번: 스택 수열

1부터 n까지의 수를 오름차순으로 스택에 넣었다가 뽑아 늘어놓으면서, 주어진 수열과 같게 만들 수 있을지 구하기

 

문제 풀이법

수를 넣었다 뽑을 stack, 주어진 수열을 담을 vector, 연산 과정을 넣어줄 vector가 필요하다

 

우선 주어진 수에 맞게 while문을 돌도록 한다.

단, while문을 한바퀴 돌았다고 해서 idx를 + 1하는 것이 아니라, 주어진 수열(v)의 인덱스의 값과, 스택에서 뽑은 값이 같을 때만 idx를 + 1 한다

스택의 top을 이용해 비교할 것이므로 0을 넣어서 셋팅해준다 (아무것도 없으면 s.top() 자체가 불가능 하기 때문)

• 만일 스택의 top이 v[idx] 보다 작으면 1부터 오름차순으로 스택에 값을 넣어준다
• 만일 스택의 top이 v[idx] 보다 크면 현재 스택이 비어있는지, 아니면 초기 상태인 0이 들어있는지 확인하고 pop해준다
• 만일 스택의 top이 v[idx]와 같다면 pop해준 후, idx + 1 해준다

while문을 돌면서 넣을 수 있는 값이 n보다 크거나, 더 이상 pop 할 수 없을 때는 주어진 수열을 만들 수 없으므로 NO를 출력하고 종료한다

 

소스 코드

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

using namespace std;

int main()
{
    int n;
    
    cin >> n;
    
    stack<int> s;
    vector<int> v;
    vector<char> ans;
    
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    int idx = 0;
    int j = 1;
    s.push(0);
    
    while (idx < n)
    {
        if (j > n + 1)
        {
            printf("NO\n");
            return 0;
        }
        
        if (s.top() < v[idx])
        {
            s.push(j);
            ans.push_back('+');
            j++;
        }
        else if (s.top() > v[idx])
        {
            if (s.top() == 0 || s.empty())
            {
                printf("NO\n");
                return 0;
            }
            s.pop();
            ans.push_back('-');
        }
        else
        {
            s.pop();
            ans.push_back('-');
            idx++;
        }
    }
    
    for (int i = 0; i < ans.size(); i++)
    {
        printf("%c\n", ans[i]);
    }
    
}