[백준 11286] 절댓값 힙 (Java) - PriorityQueue 커스텀 정렬 마스터하기

🚀 문제 핵심

일반적인 힙(Heap)이 최솟값이나 최댓값을 빠르게 꺼내는 데 집중한다면, 이 문제는 '절댓값'이라는 새로운 기준을 제시합니다.

1. 절댓값이 가장 작은 값을 우선적으로 출력한다.
2. 만약 절댓값이 같다면, 그중 실제 값이 가장 작은(음수) 값을 우선적으로 출력한다.
3. 데이터 개수 $N$이 100,000개이므로, 매번 정렬할 수 없고 삽입/삭제가 $O(\log N)$인 힙 자료구조를 사용해야 한다.

---

💡 해결 전략: Comparator 재정의 (Custom Sorting)

Java의 PriorityQueue는 기본적으로 낮은 숫자가 우선순위를 갖는 Min-Heap으로 동작합니다. 하지만 생성자에서 Comparator를 재정의하면 우리가 원하는 복잡한 우선순위를 주입할 수 있습니다.

1. 정렬 기준 설계 (Priority Logic)

• 비교 대상: $a$와 $b$
• 기준 1: Math.abs(a)와 Math.abs(b)를 비교하여 다르면 절댓값이 작은 순서대로 정렬합니다.
• 기준 2: 절댓값이 같다면 a와 b 자체를 비교하여 더 작은 값(음수)이 우선순위를 갖게 합니다.

2. 효율성

• PriorityQueue는 내부적으로 이진 트리 기반의 힙 구조를 유지합니다.
• 삽입(add)과 삭제(poll) 모두 $O(\log N)$이므로, 전체 시간 복잡도는 $O(N \log N)$이 되어 시간 제한 내에 충분히 통과합니다.

---

💻 구현 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            
            int N = Integer.parseInt(br.readLine());
            
            // PriorityQueue 생성 시 람다식을 이용한 커스텀 정렬 정의
            Queue<Integer> pq = new PriorityQueue<>((a, b) -> {
                int absA = Math.abs(a);
                int absB = Math.abs(b);

                if (absA != absB) {
                    // 1. 절댓값이 다르면 절댓값 기준 오름차순
                    return absA - absB;
                }
                // 2. 절댓값이 같으면 실제 값 기준 오름차순 (음수 우선)
                return a - b;
            });

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < N; i++) {
                int x = Integer.parseInt(br.readLine());
                
                if (x == 0) {
                    // 큐가 비어있으면 0, 아니면 최우선순위 값 추출
                    sb.append(pq.isEmpty() ? 0 : pq.poll()).append("\n");
                } else {
                    pq.add(x);
                }
            }

            bw.write(sb.toString());
            bw.flush();
        }
    }
}

---

🧐 기술적 고찰

• Comparator의 반환값 이해:
• return a - b; (오름차순): 결과가 음수면 $a$가 앞, 양수면 $b$가 앞으로 갑니다.
• return b - a; (내림차순): 결과가 음수면 $b$가 앞, 양수면 $a$가 앞으로 갑니다.
• 이 원리를 이용해 절댓값 비교 후 조건부 반환을 설정하는 것이 핵심입니다.

• 성능 최적화:
• 대량의 I/O 처리를 위해 BufferedReader와 StringBuilder를 사용했습니다. 특히 PriorityQueue는 System.out.println을 반복 호출할 때 발생하는 오버헤드를 줄이는 것만으로도 성능 체감이 큽니다.

---

🎯 마치며

이번 문제는 단순한 자료구조 사용법을 넘어, 개발자가 원하는 형태로 자료구조의 내부 로직을 커스터마이징하는 능력을 기르기 좋습니다. 스택, 큐, 덱 그리고 이번 우선순위 큐까지 정리하면서 '상황에 맞는 최적의 자료구조 선택'에 대한 자신감을 얻을 수 있었습니다.