백준 18258번: 큐 2

정수를 저장하는 큐(Queue)를 구현하고, 6가지 종류의 명령에 따라 결과를 출력하는 문제입니다. 자료구조의 기본인 큐의 FIFO(First-In, First-Out) 특성을 이해하고, Java의 ArrayDeque를 활용하여 각 기능을 효율적으로 구현하는 것이 핵심입니다.

---

✅ 문제 개요

항목	내용
문제 번호	18258번 - 큐 2
난이도	실버 4
핵심 알고리즘	자료구조, 큐, ArrayDeque

---

✅ 문제 설명 요약

• 입력:
  1. 첫째 줄: 명령의 수 N (1 ≤ N ≤ 2,000,000)
  2. 이후 N개의 줄: 6가지 종류의 명령이 주어짐
• 출력: pop, size, empty, front, back 명령에 대한 결과를 한 줄에 하나씩 출력
• 명령 규칙:
  • push X: 정수 X를 큐에 넣는다.
  • pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력. 없으면 -1 출력.
  • size: 큐에 들어있는 정수의 개수를 출력.
  • empty: 큐가 비어있으면 1, 아니면 0을 출력.
  • front: 큐의 가장 앞에 있는 정수를 출력. 없으면 -1 출력.
  • back: 큐의 가장 뒤에 있는 정수를 출력. 없으면 -1 출력.

---

✅ 풀이 전략

이 문제는 큐의 6가지 기본 연산을 구현하는 문제입니다. 특히 N이 200만으로 매우 크기 때문에, 모든 연산이 O(1)에 가까운 시간 복잡도를 가지는 효율적인 자료구조를 선택해야 합니다.

1️⃣ 핵심 자료구조: ArrayDeque로 큐 구현

• 큐는 FIFO (First-In, First-Out), 즉 '먼저 들어온 것이 가장 먼저 나가는' 구조입니다.
• Java에서 큐를 구현할 때는 LinkedList보다 삽입/삭제 성능이 더 우수한 ArrayDeque를 사용하는 것이 권장됩니다.
• 특히 이 문제의 back 연산은 큐의 맨 뒤 원소를 확인해야 하는데, ArrayDeque는 Deque(Double-Ended Queue) 인터페이스를 구현하므로 peekLast() 메소드를 통해 이 기능을 O(1)에 쉽게 처리할 수 있습니다.

2️⃣ ArrayDeque와 명령어 매핑

• ArrayDeque가 제공하는 메소드들은 문제의 6가지 명령을 완벽하게 지원합니다.

명령어	동작	java.util.ArrayDeque 메소드	비어있을 때 처리
push X	X를 큐의 뒤에 넣음	queue.offer(X)	-
pop	맨 앞 정수를 빼고 출력	queue.poll()	-1 출력
size	큐의 크기 출력	queue.size()	0 출력
empty	큐가 비었는지 확인	queue.isEmpty()	1 출력
front	맨 앞 정수를 확인만 함	queue.peek()	-1 출력
back	맨 뒤 정수를 확인만 함	queue.peekLast()	-1 출력

3️⃣ 알고리즘 설계

1. Deque<Integer> q = new ArrayDeque<>(); 와 같이 ArrayDeque 객체를 생성합니다.
2. 명령의 수 N을 입력받고, N번 반복하는 for문을 실행합니다.
3. switch 문을 사용하여 입력된 명령어에 따라 로직을 분기합니다.
4. 각 case에서 해당하는 ArrayDeque 메소드를 호출합니다.
5. pop, front, back의 경우, 큐가 비어있는지(q.isEmpty()) 먼저 확인하고, 비어있다면 -1을, 아니라면 메소드 호출 결과를 BufferedWriter에 작성합니다.
6. 모든 명령이 끝나면 BufferedWriter의 내용을 출력(flush)합니다.

---

✅ Java 코드 예제

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        // 큐로 사용할 Deque 선언
        Deque<Integer> q = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            switch (command) {
                case "push":
                    q.offer(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    if (q.isEmpty()) {
                        bw.write("-1\n");
                    } else {
                        bw.write(q.poll() + "\n");
                    }
                    break;
                case "size":
                    bw.write(q.size() + "\n");
                    break;
                case "empty":
                    if (q.isEmpty()) {
                        bw.write("1\n");
                    } else {
                        bw.write("0\n");
                    }
                    break;
                case "front":
                    if (q.isEmpty()) {
                        bw.write("-1\n");
                    } else {
                        bw.write(q.peek() + "\n");
                    }
                    break;
                case "back":
                    if (q.isEmpty()) {
                        bw.write("-1\n");
                    } else {
                        bw.write(q.peekLast() + "\n");
                    }
                    break;
            }
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
}

---

⚠️ 실전 주의사항

항목	설명
입출력 성능	N이 200만으로 매우 크므로, Scanner와 System.out.println을 반복 사용하면 반드시 시간 초과가 발생합니다. BufferedReader와 BufferedWriter 사용이 필수적입니다.
ArrayDeque 활용	큐의 back 기능은 표준 Queue 인터페이스에는 없습니다. 하지만 ArrayDeque는 Deque 인터페이스를 구현하므로 peekLast() 메소드를 통해 O(1)에 효율적으로 back 기능을 구현할 수 있습니다. 이것이 이 문제에서 ArrayDeque를 써야 하는 핵심 이유입니다.
poll vs remove	큐가 비어있을 때 poll()은 null을 반환하는 반면 remove()는 예외(NoSuchElementException)를 발생시킵니다. 조건문으로 -1을 처리해야 하는 문제에서는 poll()이 더 안전하고 편리합니다.
명령어 파싱	push 명령어는 정수 X를 추가로 받으므로, StringTokenizer를 사용하여 공백을 기준으로 명령어를 분리해야 합니다.

---

📝 마무리 요약

✔️ 큐의 FIFO(First-In, First-Out) 특성을 이해하고 구현하는 문제입니다.
✔️ Java에서는 ArrayDeque를 Deque 타입으로 선언하여 사용하는 것이 back 기능까지 효율적으로 처리할 수 있어 가장 좋습니다.
✔️ push는 offer, pop은 poll, front는 peek, 그리고 back은 peekLast 메소드에 대응됩니다.
✔️ 명령의 수가 매우 많으므로 빠른 입출력 처리가 시간 초과를 방지하는 열쇠입니다.