백준 15828 Router Java: 제한된 Buffer를 Queue로 시뮬레이션하기

백준 15828번 ‘Router’는 크기가 정해진 buffer에 packet을 넣고 처리하는 과정을 simulation한다. 들어온 packet number는 queue 뒤에 넣고, 0이면 가장 앞 packet을 처리하며, -1이면 입력을 끝낸다.

• 백준 15828번 Router

입력값별 동작

입력	동작
양수	buffer에 빈자리가 있으면 뒤에 추가, 가득 차면 버림
0	buffer가 비어 있지 않으면 앞 packet 제거
-1	simulation 종료

queue의 실제 크기를 size()로 확인하면 별도의 packetCount를 동기화할 필요가 없다. 두 상태를 따로 관리하면 한쪽만 갱신하는 branch에서 오류가 생길 수 있다.

Java 코드

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

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

        while (true) {
            int input = Integer.parseInt(reader.readLine());

            if (input == -1) {
                break;
            }

            if (input == 0) {
                buffer.pollFirst();
            } else if (buffer.size() < capacity) {
                buffer.offerLast(input);
            }
        }

        if (buffer.isEmpty()) {
            System.out.println("empty");
            return;
        }

        StringBuilder output = new StringBuilder();
        while (!buffer.isEmpty()) {
            if (output.length() > 0) {
                output.append(' ');
            }
            output.append(buffer.pollFirst());
        }

        System.out.println(output);
    }
}

pollFirst()는 deque가 비었으면 exception 대신 null을 반환하므로 0 입력에서 별도 empty branch 없이 호출해도 된다. return value를 쓰지 않기 때문에 안전하다.

원문 구현에서 단순화한 부분

원문은 LinkedList queue와 별도 packetCount를 함께 사용했다. 0일 때 queue를 poll하고 count가 0 아래로 내려가지 않게 ternary로 막았다. queue 자체가 이미 크기를 알고 있으므로 count는 중복 상태다.

출력에서도 빈 buffer일 때 "empty "를 먼저 넣고 마지막 문자를 지우는 방식 대신, empty를 바로 출력하고 값 사이에만 공백을 넣었다. 마지막 공백을 잘라내는 code는 출력이 하나도 없을 때 index 오류를 만들기 쉽다.

명령 수를 Q라고 하면 각 queue operation은 amortized O(1), 전체 시간은 O(Q), 공간은 capacity에 비례한 O(N)이다.

오랜만에 Queue를 다시 쓴 기록

원문에는 오랜만에 queue와 StringBuilder를 사용해 푼 문제라고 적혀 있다. router의 실제 network behavior를 학습했다고 넓혀 말하기보다, bounded FIFO buffer의 accept·drop·consume 규칙을 자료구조로 옮긴 문제라고 보는 것이 정확하다.

queue command를 직접 구현하는 문제는 백준 18258 큐 2, 양끝을 모두 쓰는 deque 문제는 백준 1021 회전하는 큐에서 이어진다.

검증 범위

Java source를 수동 검토하고 empty buffer의 zero, full buffer drop, consume 후 새 packet 수용과 random event stream을 bounded array reference model과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.