스택 수열 1874

문제

접근 방법

결과로 나타나야 할 수열을 A
1부터 n까지 순서대로 들어갈 수열을 B라고 하면 A의 값 a가 B의 값 b보다 크거나 같다면 b는 a의 값까지 스택에 넣어주면 된다. 그 후 하나를 빼주면 a의 값과 같은 값을 빼주는 것이다.

만약 크거나 같지 않다면 스택에 있는 값이 a보다 작은지 확인해 준다.

현재 b가 5이고 스택의 값이 3이라면 5까지 입력하고 2개를 뺀 형태이다. (3 밑의 수를 고려하지 않는다면 말이다)
그런 상황에서 4가 나온다면 5를 높여서 얻을 수도, 스택에서 빼서 얻을 수도 없으니 불가능한 경우이다.

불가능한 경우가 아니면 a까지 스택의 값을 빼주면 된다.

코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n, num = 1, k;
    cin >> n;
    vector<int> stack;
    vector<char> ret;
    for (int i = 1; i <= n; ++i)
    {
        cin >> k;
        if (num <= k)
        {
            while (num <= k)
            {
                stack.push_back(num++);
                ret.push_back('+');
            }
            stack.pop_back();
            ret.push_back('-');
        }
        else
        {
            if (stack.empty() || stack.back() < k)
            {
                cout << "NO";
                return 0;
            }
            while (!stack.empty() && stack.back() >= k)
            {
                stack.pop_back();
                ret.push_back('-');
            }
        }
    }
    for (char c : ret)
        cout << c << "\n";
    return 0;
}

풀이

졸려서 그런 것 같기도 하지만 간단하게 설명하기 어려운 문제 같다.
어떠한 특징을 가졌는지 파악하고 풀면 된다.