백준 25556번 포스택 C++ (골드5)

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

 

스택에서 뺀 뒤에 뒤에서부터 배치하여 오름차순이 되어야 하기 때문에 스택에 top에는 큰 수가 들어있어야 하고, 작은 수를 되도록 스택에 먼저 넣어야 한다.

 

만약 스택에 수를 넣을때 스택의 top이 지금 넣을 수보다 크다면 뺄때 오름차순이 불가능하다.

그렇기 때문에 스택에 수를 넣을때 스택의 top이 지금 넣을 수보다 작다고 무조건 넣으면 안되고 스택의 top이 지금 넣을 수보다 작은 수중 제일 큰 수를 찾아서 해당 스택에 넣어야 한다.

 

이렇게 진행하다가 만약 모든 스택의 top이 지금 넣을 수보다 크다면 꺼냈을때 오름차순이 불가능하다.

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;
vector<int> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<stack<int>> sv(4);

    cin >> n;
    v = vector<int>(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
    bool possible = true;
    for (int i = 0; i < n; i++)
    {
        int num = v[i];
        int maxNum = -1;
        int idx = -1;
        for (int j = 0; j < 4; j++)
        {
            if (sv[j].empty())
            {
                if (maxNum < 0)
                {
                    maxNum = 0;
                    idx = j;
                }
            }
            else {
                if (sv[j].top() < num)
                {
                    if (maxNum < sv[j].top())
                    {
                        maxNum = sv[j].top();
                        idx = j;
                    }
                }
            }
        }
        if (idx == -1) {
            possible = false;
            break;
        }
        sv[idx].push(num);
    }
    if (possible) cout << "YES";
    else cout << "NO";
}