[BaekJoon] 12789번 - 도키도키 간식드리미 [Java][C++]

문제 링크

---

1. 문제 풀이

임시 공간을 활용해서 주어진 순서를 오름차순으로 만들 수 있는지 구하는 문제로 스택을 활용한 스택 순열 문제의 일종이다. $1$ 부터 $N$ 까지 각 번호에 대해 현재 스택의 가장 윗 번호와 일치하면 스택에서 꺼내서 대기시키고 아니면 줄 서있는 곳의 사람들 중 해당 번호가 나올 때까지 스택에 넣다가 해당 번호가 나오면 넣으면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Deque<Integer> stack = new ArrayDeque<>();
        int idx = 0;
        boolean isPossible = true;

        for (int need = 1; need <= N; need++) {
            if (!stack.isEmpty() && stack.peek() == need) {
                stack.pop();
            } else {
                while (idx < N && arr[idx] != need) {
                    stack.push(arr[idx++]);
                }

                if (idx == N) {
                    isPossible = false;
                    break;
                }
                idx++;
            }
        }

        if (isPossible) {
            System.out.println("Nice");
        } else {
            System.out.println("Sad");
        }
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> v(n);
    for (int& x : v) cin >> x;

    stack<int> st;
    int idx = 0;
    bool flag = true;

    for (int need = 1; need <= n; need++) {
        if (!st.empty() && st.top() == need) {
            st.pop();
        } else {
            while (idx < n && v[idx] != need) {
                st.push(v[idx++]);
            }

            if (idx == n) {
                flag = false;
                break;
            }
            idx++;
        }
    }

    if (flag) {
        cout << "Nice";
    } else {
        cout << "Sad";
    }
}

---