[백준 Java]_크리스마스 선물 (14235)

문제 정보

• 출처 및 난이도: 백준 실버3
• 링크: https://www.acmicpc.net/problem/14235
• 분류: 우선순위 큐, 자료 구조

---

문제 요약

산타가 선물을 충전하고 아이들에게 나눠주는 문제.

• 입력값이 0이면 현재 가진 선물 중 가장 가치 높은 것 을 줌
• 선물이 없으면 -1 출력
• 입력값이 N이면 N개의 선물 가치를 충전

---

풀이 접근

1. 이벤트를 순서대로 처리
2. 입력이 0이면 give() 호출 → 최댓값 poll 또는 -1 출력
3. 입력이 N이면 이어지는 N개의 값을 최대 힙에 offer

---

우선순위 큐?

우선순위 큐(Priority Queue)는 원소들에게 우선순위를 매겨서 넣을 때의 순서와 상관없이 뺄 때에는 우선순위가 높은 원소부터 빼는 것이다. 대표적인 예로 Heap이 있다.

import java.util.*;

// 최소 힙 (기본)
PriorityQueue<Integer> minPq = new PriorityQueue<>(); 

// 최대 힙
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder()); 

<주요 메서드>

• pq.offer(item): 삽입
• pq.poll(): 최솟값/최댓값 꺼내기 (제거 O)
• pq.peek(): 최솟값/최댓값 확인 (제거 X)
• pq.isEmpty(): 비어있는지 확인
• pq.size(): 크기

---

핵심 아이디어

• 항상 가장 가치 높은 선물을 줘야 하므로 최대 힙(Max Heap) 사용
• Java의 PriorityQueue는 기본이 최소 힙이라 Collections.reverseOrder() 로 최대 힙으로 변환
• 선물이 없을 때 -1 반환하는 예외 처리만 신경쓰면 구조 자체는 단순

---

코드

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < n; i++) {
            int a = scanner.nextInt();
            if (a == 0) System.out.println(give(pq));
            else
                for(int j = 0; j < a; j++) {
                    pq.offer(scanner.nextInt());
                }
        }
        scanner.close();
    }

    public static int give(PriorityQueue<Integer> pq) {
        if (pq.isEmpty()) return -1;
        else return pq.poll();
    }
}

---

배운 점 / 회고

• 최대/최소 힙 선택이 핵심인 전형적인 우선순위 큐 문제
• Java에서 최대 힙을 만들려면 new PriorityQueue<>(Collections.reverseOrder()) 또는 new PriorityQueue<>((a, b) -> b - a) 를 써야 한다.