[백준] 11286번 - 절댓값 힙 풀이 및 코드 분석 (Java)

문제 링크

---

1. 문제 분석

📌 문제 개요

절댓값 힙은 절댓값이 작은 순서대로 값을 정렬하는 힙(우선순위 큐)이다.
만약 절댓값이 동일하다면 값이 작은 수가 우선순위를 갖는다.
이 힙을 이용해 주어진 연산을 수행하는 프로그램을 작성해야 한다.

🎯 요구사항

1. 정수 x를 힙에 추가 (x ≠ 0일 경우)
2. 절댓값이 가장 작은 값 출력 & 삭제 (x == 0일 경우)
   • 같은 절댓값을 가진 값이 여러 개일 경우, 값이 작은 수를 먼저 출력
   • 힙이 비어 있다면 0을 출력
3. N의 최대 크기가 100,000이므로 O(log N) 이하의 연산 속도가 필요하다.

---

2. 해결 방법

🔹 핵심 개념

우선순위 큐(Priority Queue) 를 활용하여 데이터를 정렬하고 관리할 수 있다.
우선순위 큐에서 커스텀 정렬을 적용하여, 절댓값이 작은 순서 + 값이 작은 순서로 정렬한다.

🔑 해결 절차

1. 우선순위 큐(PriorityQueue) 생성
   • PriorityQueue<Integer>를 생성하고, Comparator를 사용해 절댓값 기준 오름차순 정렬
   • 만약 절댓값이 같다면, 값이 작은 순서로 정렬
2. 입력값 처리 및 연산 수행
   • x ≠ 0이면 우선순위 큐에 추가
   • x == 0이면 우선순위 큐에서 최상위 값을 꺼내 출력
   • 큐가 비어 있으면 0을 출력
3. 시간 복잡도 최적화
   • 삽입/삭제 연산 → O(log N)
   • N개의 연산 수행 → O(N log N) → N ≤ 100,000이므로 충분히 빠르게 동작

---

3. 코드 구현

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder(); // 출력 속도 최적화를 위한 StringBuilder 사용

        int N = Integer.parseInt(br.readLine()); // 연산 개수
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
            if (Math.abs(a) == Math.abs(b)) return a - b; // 절댓값이 같다면 더 작은 값이 우선
            return Math.abs(a) - Math.abs(b); // 절댓값 기준 오름차순 정렬
        });

        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());

            if (x != 0) {
                pq.offer(x); // 힙에 추가
            } else {
                sb.append(pq.isEmpty() ? 0 : pq.poll()).append("\n"); // 최소 절댓값 출력
            }
        }

        System.out.print(sb); // 한 번에 출력하여 시간 최적화
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. 우선순위 큐(PriorityQueue) 사용
   • Comparator를 사용해 정렬 기준 설정
     • Math.abs(a) - Math.abs(b): 절댓값 오름차순
     • a - b: 절댓값이 같을 경우, 작은 값 우선순위
2. 입력 및 연산 처리
   • x ≠ 0: 힙에 추가
   • x == 0: 힙에서 가장 작은 값 출력 (없으면 0)
3. 출력 최적화 (StringBuilder 사용)
   • System.out.println()을 여러 번 호출하면 시간 초과 가능성이 있음
   • StringBuilder에 결과를 저장 후, 한 번에 출력하여 속도 최적화

🔹 시간 복잡도 분석

연산	시간 복잡도	설명
offer(x)	O(log N)	힙에 삽입
poll()	O(log N)	최소값 제거
N번 수행	O(N log N)	최대 100,000번 연산 가능

 

👉 O(N log N)의 시간 복잡도로 문제 조건(N ≤ 100,000)에 적합함.

---

5. 개선할 점 및 대체 방법

✅ 개선할 점

1. Heap 대신 TreeSet 활용 가능
   • TreeSet<Integer>를 사용하면 정렬된 상태 유지 + 빠른 삭제가 가능
   • 하지만 PriorityQueue가 메모리 사용량이 적고, 성능도 유사하므로 일반적으로 더 선호됨
2. Heapify 최적화
   • 기본적으로 Java의 PriorityQueue는 Min-Heap 구조를 사용
   • Max-Heap이 필요한 경우 Collections.reverseOrder()를 활용 가능
3. 배열 기반 힙 구현 가능
   • 직접 Min-Heap을 구현하면 불필요한 객체 생성 방지 가능
   • 하지만 우선순위 큐가 내부적으로 최적화되어 있어, 직접 구현할 필요는 없음

🔄 대체 방법

1. TreeMap 사용
   • TreeMap<Integer, PriorityQueue<Integer>> 구조를 활용하면 더 빠르게 정렬 가능
   • 하지만 PriorityQueue만으로도 충분히 빠른 성능을 제공하므로 필요 없음