백준 11286 절댓값 힙 Java: Comparator의 두 정렬 기준

백준 11286번 ‘절댓값 힙’은 0이 아닌 수를 저장하고, 0이 들어오면 절댓값이 가장 작은 수를 꺼낸다. 절댓값이 같으면 원래 값이 더 작은 수, 즉 음수를 먼저 꺼내야 한다.

• 백준 11286번 절댓값 힙

PriorityQueue의 comparator에 절댓값 오름차순, 원래 값 오름차순 두 기준을 차례로 넣으면 된다.

Comparator를 subtraction으로 쓰지 않기

정렬 기준이 두 개라면 첫 비교가 같을 때만 두 번째 비교로 넘어간다.

PriorityQueue<Long> heap = new PriorityQueue<>((left, right) -> {
    int byAbsolute = Long.compare(Math.abs(left), Math.abs(right));

    if (byAbsolute != 0) {
        return byAbsolute;
    }

    return Long.compare(left, right);
});

(int) (left - right)처럼 차를 반환하면 범위에 따라 overflow가 나거나 long 차이가 잘릴 수 있다. Long.compare()는 비교 의도를 그대로 표현한다.

Java 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

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

        PriorityQueue<Long> heap = new PriorityQueue<>((left, right) -> {
            int byAbsolute = Long.compare(
                    Math.abs(left),
                    Math.abs(right)
            );

            if (byAbsolute != 0) {
                return byAbsolute;
            }

            return Long.compare(left, right);
        });

        StringBuilder output = new StringBuilder();

        for (int operation = 0; operation < operationCount; operation++) {
            long value = Long.parseLong(reader.readLine());

            if (value != 0) {
                heap.offer(value);
            } else if (heap.isEmpty()) {
                output.append(0).append('\n');
            } else {
                output.append(heap.poll()).append('\n');
            }
        }

        System.out.print(output);
    }
}

문제의 정수 범위에는 int도 사용할 수 있지만, 원문에서 자료형 경계를 헷갈렸던 학습 지점을 살리고 절댓값 overflow 가능성을 넉넉히 피하기 위해 long으로 작성했다. 일반적으로 Long.MIN_VALUE는 Math.abs()를 해도 양수가 되지 않지만 이 문제 입력 범위에는 포함되지 않는다.

Comparable class가 꼭 필요한가

원문은 원래 값과 절댓값을 저장한 Node를 만들고 Comparable<Node>를 구현했다. 여러 field와 domain 의미가 있는 객체라면 좋은 선택이다. 하지만 여기서는 원래 값 하나로 절댓값을 언제든 계산할 수 있어 PriorityQueue<Long>과 comparator만으로 충분하다.

또 원문 comparator는 같지 않은 두 값에도 -1 또는 1만 반환했고, 완전히 같은 값일 때도 0을 반환하지 않았다. comparator contract를 지키려면 같은 두 값은 0이어야 한다. Long.compare()를 조합하면 이 조건도 자연스럽게 만족한다.

문제를 제대로 읽지 않아 반복한 오답

원문에는 50분 timer에서 31분 14초가 남아 있었으므로 약 19분가량 사용한 기록이 있다. 처음에는 자료형 범위를 잘못 기억했고, 절댓값이 같을 때 원래 값이 작은 수를 먼저 꺼내는 두 번째 조건도 놓쳐 여러 번 틀렸다고 적었다.

우선순위 queue 문제에서는 “가장 작은 값”이라는 한 문장보다 정렬 key의 순서와 tie-breaker를 먼저 써 두는 편이 안전하다. Java의 비교 방식 자체는 compareTo와 Comparator 정리, 두 heap으로 중앙값을 유지하는 응용은 백준 1655 가운데를 말해요에서 이어진다.

복잡도와 검증 범위

삽입과 삭제는 각각 O(log N), 빈 heap 확인은 O(1), 저장 공간은 O(N)이다. Java source를 수동 검토하고 같은 절댓값의 음수·양수, duplicate, 빈 heap 출력과 작은 random operation을 직접 정렬한 multiset oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.