백준 18258 큐 2 Java: ArrayDeque와 빠른 입출력

백준 18258번은 여섯 가지 명령으로 큐의 선입선출 동작을 구현하는 문제다. 원문에서는 같은 코드를 삼항 연산자 사용 전후로 나눠 보았다. 다시 정리해 보니 핵심은 표현식의 길이가 아니라 큐의 양 끝을 어떻게 다루고, 최대 200만 개의 명령을 어떻게 한꺼번에 출력하느냐에 있었다.

• 백준 18258번 큐 2

배열과 두 인덱스로 큐 자체를 구현하는 방법은 백준 18258 배열 큐 풀이에 따로 남겼다. 이 글에서는 Java 표준 자료구조인 ArrayDeque를 사용한다.

명령을 Queue 연산으로 그대로 옮긴다

ArrayDeque에서는 앞과 뒤를 메서드 이름으로 분명하게 드러낼 수 있다.

명령	ArrayDeque 연산	비어 있을 때
push X	addLast(X)	해당 없음
pop	removeFirst()	-1 출력
size	size()	0
empty	isEmpty()	1
front	getFirst()	-1 출력
back	getLast()	-1 출력

push는 뒤에 넣고 pop은 앞에서 꺼낸다. 이 두 방향만 흔들리지 않으면 나머지 명령은 현재 상태를 조회하는 일이다.

Java 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int commandCount = Integer.parseInt(reader.readLine());
        Deque<Integer> queue = new ArrayDeque<>();
        StringBuilder output = new StringBuilder();

        for (int i = 0; i < commandCount; i++) {
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );
            String command = tokenizer.nextToken();

            if (command.equals("push")) {
                queue.addLast(Integer.parseInt(tokenizer.nextToken()));
            } else if (command.equals("pop")) {
                output.append(
                        queue.isEmpty() ? -1 : queue.removeFirst()
                ).append('\n');
            } else if (command.equals("size")) {
                output.append(queue.size()).append('\n');
            } else if (command.equals("empty")) {
                output.append(queue.isEmpty() ? 1 : 0).append('\n');
            } else if (command.equals("front")) {
                output.append(
                        queue.isEmpty() ? -1 : queue.getFirst()
                ).append('\n');
            } else if (command.equals("back")) {
                output.append(
                        queue.isEmpty() ? -1 : queue.getLast()
                ).append('\n');
            }
        }

        System.out.print(output);
    }
}

빠른 입출력이 풀이의 일부다

이 문제는 명령 수가 최대 200만 개다. 매번 System.out.println()을 호출하기보다 결과를 StringBuilder에 모았다가 한 번에 출력하면 출력 호출 횟수를 줄일 수 있다. 입력도 정규식 기반 split()을 반복하기보다 BufferedReader와 StringTokenizer로 읽었다.

모든 deque 연산은 끝에서 수행하므로 명령 하나당 상수 시간이다. 전체 시간 복잡도는 O(N), 큐가 차지하는 추가 공간은 최악의 경우 O(N)이다.

직접 구현과 ArrayDeque 중 무엇을 고를까

문제의 목적이 큐의 인덱스 불변식을 익히는 것이라면 배열로 직접 구현해 볼 가치가 있다. 반대로 이미 큐의 동작을 알고 있고 명령 처리에 집중하려면 ArrayDeque가 코드 의도를 더 잘 드러낸다.

원문의 삼항 연산자 버전과 if 버전은 결과와 복잡도가 같다. 이 선택은 성능 기법이라기보다 읽기 방식의 차이다. 빈 큐 처리 규칙이 반복되더라도, 각 명령이 무엇을 반환하는지 바로 보이는 쪽을 택하는 편이 낫다.

개편 과정에서는 빈 큐 조회, 연속 push·pop, 중복 값, 다시 채우는 명령 흐름을 기준 큐와 대조했다. 현재 환경에는 실제 JDK와 BOJ 재제출 결과가 없어 Java 컴파일·채점 통과 여부는 별도 확인이 필요하다.