BOJ 31719 : UDP 스택

• 문제 링크 : boj.kr/31719
• 난이도 : G4
• 태그 : 그리디, 시뮬레이션

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        vector<int> arr(n);
        for(auto &u : arr) cin >> u;

        bool ans = true;
        int target = 1;
        pii st[2] = {};
        for(int i = 0; i < n; i++) {
            if(arr[i] == target) {
                target += 1;
                continue;
            }
            if(st[0].first == target) {
                target = st[0].second + 1;
                st[0] = st[1];
                st[1] = {0,0};
            }
            else if(st[1].first == target) {
                target = st[1].second + 1;
                st[1] = {0,0};
            }
            bool check = true;
            for(int j = 0; j < 2; j++) {
                if(st[j].first == 0) {
                    st[j].first = st[j].second = arr[i];
                    check = false;
                    break;
                }
                else if(st[j].second + 1 == arr[i]) {
                    st[j].second += 1;
                    check = false;
                    break;
                }
            }
            if(check) {
                ans = false;
                break;
            }
        }
        cout << (ans ? "YES" : "NO") << "\n";
    }

    return 0;
}

---

풀이

열려있는 스택은 bypass 상태이므로 고려할 필요가 없다. 따라서 실질적인 스택은 두 개이다.

현재 보고있는 원소가 떨어뜨려야 하는 원소라면 열려있는 스택으로 통과시킨다.

그렇지 않다면 스택에 넣어줄 수 있는지 확인한다.

어떤 원소가 스택에 들어가려면 스택의 가장 위 원소가 자신보다 1 작아야 하거나, 스택이 비어있어야 한다.

 

원소를 어떤 스택에 넣을지 결정하기 전에 스택을 열 수 있는지 확인한다. 스택의 가장 아래 원소가 떨어뜨려야 하는 원소라면 스택을 열 수 있다.

 

위 과정에서 원소를 스택에 넣지 못한다면 불가능한 경우이다. 순서대로 시뮬레이션 하면 된다.