[BaekJoon] 1874번 - 스택 수열 [Java][C++]

문제 링크

---

1. 아이디어

전형적인 스택 순열 문제로 1부터 N까지 순서대로 삽입할 수 있으므로 현재 삽입할 수를 나타내는 변수 cur를 활용하면 해결할 수 있다. 수열의 각 수 x에 대해 cur가 x보다 작다면 일단 cur가 x가 될 때까지 1씩 증가시키며 삽입해야 한다. 삽입을 한 후 top을 제거하면 되는데 삽입에 실패할 경우에는 이미 top이 x와 같은 경우와 아닌 경우가 있다. 같은 경우는 해당 수도 제거하면 되며 같지 않으면 스택으로 만들 수 없는 수열이다.

---

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));
        StringBuilder sb = new StringBuilder();

        Deque<Integer> stack = new ArrayDeque<>();
        int cur = 1;

        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            int x = Integer.parseInt(br.readLine());

            while (cur <= x) {
                stack.push(cur++);
                sb.append("+\n");
            }

            if (stack.peek() != x) {
                System.out.println("NO");
                return;
            }

            stack.pop();
            sb.append("-\n");
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

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

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

    stack<int> st;
    string ans;
    int cur = 1;

    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;

        while (cur <= x) {
            st.push(cur++);
            ans += "+\n";
        }

        if (st.top() != x) {
            cout << "NO";
            return 0;
        }

        st.pop();
        ans += "-\n";
    }

    cout << ans;
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---