[백준 Java]_덱 (10866)

문제 정보

• 출처 및 난이도: 백준 실버4
• 링크: https://www.acmicpc.net/problem/10866
• 분류: 덱, 자료구조, 구현

---

문제 요약

• 정수를 저장하는 덱을 구현하는 문제.
• push_front, push_back, pop_front, pop_back, size, empty, front, back
• 8가지 명령어를 처리하고, 비어있는 덱에 pop/front/back 시도하면 -1 출력.

---

풀이 접근

1. 명령어를 한 줄씩 읽어 split(" ")으로 명령어와 인자 분리
2. switch문으로 각 명령어 분기 처리
3. 출력이 필요한 명령어는 StringBuilder에 append 후 마지막에 한 번에 출력

---

덱(Deque; Double Ended Queue)?

삽입은 Rear에서 출력은 Front에서만 가능한 큐에 비해, 데크는 양쪽에서 모두 삽입/출력이 가능한 스택과 큐의 특징을 모두 갖고 있다.

실사용은 아래와 같이 ArrayDeque를 이용한다.

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> dq = new ArrayDeque<>();

// 삽입
dq.addFirst(1);  // 앞에 삽입
dq.addLast(2);   // 뒤에 삽입

// 꺼내기
dq.removeFirst(); // 앞에서 꺼내기
dq.removeLast();  // 뒤에서 꺼내기

// 확인 (제거 X)
dq.peekFirst();
dq.peekLast();

// 스택처럼
dq.addFirst(1);
dq.removeFirst();

// 큐처럼
dq.addLast(1);
dq.removeFirst();

<주요 메서드>

• 삽입:
  • 앞: addFirst()
  • 뒤: addLast()
• 꺼내기:
  • 앞: removeFirst()
  • 뒤: removeLast()
• 확인:
  • 앞: peekFirst()
  • 뒤: peekLast()

---

핵심 아이디어

• ArrayDeque로 앞/뒤 삽입·삭제 모두 O(1) 처리
• 명령어 수가 최대 10,000개 → Scanner 대신 BufferedReader + StringBuilder로 I/O 최적화
• 비어있는 경우 예외처리

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

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

        Deque<Integer> deque = new ArrayDeque<>();

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

        for (int i = 0; i < N; i++) {
            String[] data = br.readLine().split(" ");
            switch (data[0]) {
                case "push_front":
                    X = Integer.parseInt(data[1]);
                    deque.addFirst(X);
                    break;
                case "push_back":
                    X = Integer.parseInt(data[1]);
                    deque.addLast(X);
                    break;
                case "pop_front":
                    if (deque.isEmpty()) {
                        sb.append(-1);
                    } else {
                        sb.append(deque.removeFirst());
                    }
                    sb.append('\n');
                    break;
                case "pop_back":
                    if (deque.isEmpty()) {
                        sb.append(-1);
                    } else {
                        sb.append(deque.removeLast());
                    }
                    sb.append('\n');
                    break;
                case "size":
                    sb.append(deque.size());
                    sb.append('\n');
                    break;
                case "empty":
                    sb.append(deque.isEmpty() ? 1 : 0);
                    sb.append('\n');
                    break;
                case "front":
                    if (deque.isEmpty()) {
                        sb.append(-1);
                    } else {
                    sb.append(deque.peekFirst());
                    }
                    sb.append('\n');
                    break;
                case "back":
                    if (deque.isEmpty()) {
                        sb.append(-1);
                    } else {
                        sb.append(deque.peekLast());
                    }
                    sb.append('\n');
                    break;
            }
        }
        System.out.print(sb);
    }
}
                                                 

참고로, 백준은 Java11을 사용하는데, 아래와 같은 -> 문법을 지원을 안해서, 클래식한 방식으로 코드를 바꿨다.

switch (data[0]) {
    case "push_front" -> {
        X = Integer.parseInt(data[1]);
        deque.addFirst(X);
    } 
}

---

배운 점 / 회고

• Java에서 Deque 인터페이스와 ArrayDeque 구현체의 메서드를 정리하는 좋은 기회였다.
• 명령어 수가 많으면 Scanner로 제출했다가 시간 초과가 날 수 있어서BufferedReader 사용을 습관화하는 것도 좋을 것 같다.
• System.out.println을 반복 호출하는 것보다 StringBuilder에 모아서 한 번에 출력하는 게 훨씬 빠르다...