[백준] 14235번 크리스마스 선물(우선순위 큐)

https://www.acmicpc.net/problem/14235

풀이

이 문제는 우선순위 큐(Priority Queue)를 이용해 최대값을 효율적으로 관리해야 하는 문제입니다. 주어진 조건에서 산타가 아이들을 만날 때마다 가장 가치가 큰 선물을 줘야 하고, 선물이 없다면 -1을 출력해야 합니다. 최대 힙(Max Heap)을 사용하면 매번 가장 큰 선물을 빠르게 찾고 제거할 수 있습니다.

문제 해결 전략

1. 문제의 요구 사항:
   • n번의 방문이 주어지며, 방문마다 두 가지 경우가 있습니다:
     1. 선물을 충전하는 경우: 이때 주어지는 선물들을 힙에 추가합니다.
     2. 아이를 만나는 경우: 현재 가지고 있는 선물 중 가장 가치가 큰 선물을 선물하고, 힙에서 제거합니다. 선물이 없으면 1을 출력합니다.
2. 자료구조 선택:
   • 가장 큰 값을 빠르게 찾아 제거해야 하므로, 최대 힙(Max Heap)이 필요합니다.
   • 자바에서는 기본적으로 PriorityQueue*는 최소 힙으로 동작하므로, 최대 힙으로 사용하기 위해 값을 음수로 변환**하여 사용합니다. 이렇게 하면 가장 큰 값이 항상 루트에 위치하게 됩니다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력 처리
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 최대 힙을 위한 우선순위 큐 (음수로 넣어 최대 힙처럼 동작)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 방문 횟수 입력
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());  // 거점지에서 충전할 선물 개수

            if (a == 0) {
                // 아이들을 만나 선물을 주는 경우
                if (maxHeap.isEmpty()) {
                    sb.append(-1).append("\n");
                } else {
                    sb.append(maxHeap.poll()).append("\n");  // 가장 큰 값(최대값) 선물
                }
            } else {
                // 거점지에서 a개의 선물을 충전하는 경우
                for (int j = 0; j < a; j++) {
                    int gift = Integer.parseInt(st.nextToken());
                    maxHeap.add(gift);  // 선물을 최대 힙에 추가
                }
            }
        }

        // 결과 출력
        System.out.println(sb);
    }
}

코드 설명

1. 입력 처리:
   • BufferedReader와 StringTokenizer를 사용하여 입력을 처리합니다.
   • n번의 입력을 처리하며, a == 0일 때 아이를 만나 선물을 주고, a > 0일 때는 거점지에서 선물을 충전합니다.
2. 우선순위 큐(PriorityQueue):
   • 자바의 PriorityQueue는 기본적으로 최소 힙을 제공합니다. 문제에서는 최대 힙이 필요하므로, Collections.reverseOrder()*를 사용하여 최대 힙**으로 동작하게 만듭니다.
   • 거점지에서 선물을 충전할 때는 선물의 가치를 그대로 PriorityQueue에 넣습니다.
   • 아이를 만날 때는 maxHeap.poll()을 사용하여 가장 큰 선물을 꺼냅니다. 만약 힙이 비어 있으면 1을 출력합니다.
3. StringBuilder를 사용한 출력 최적화:
   • 출력이 많기 때문에 매번 System.out.println을 호출하지 않고, *StringBuilder를 사용하여 결과를 모아서 한 번에 출력합니다.

시간 복잡도 분석

1. 선물 충전(삽입) 연산:
   • 선물을 PriorityQueue에 삽입하는 연산은 O(log n)의 시간이 소요됩니다. 여기서 n은 현재 힙에 있는 요소의 수입니다.
   • 한 번에 최대 100개의 선물을 충전할 수 있으므로, 최대 O(100 log n)의 시간이 소요됩니다.
2. 선물 주기(삭제) 연산:
   • 힙에서 가장 큰 값을 제거하는 연산도 O(log n)의 시간이 소요됩니다.
3. 전체 시간 복잡도:
   • n번의 입력에 대해 각각 삽입 또는 삭제 연산을 수행하므로, 전체 시간 복잡도는 O(n log n)입니다. 여기서 n은 최대 5000이므로, 이 시간 복잡도는 충분히 효율적입니다.

공간 복잡도 분석

1. 우선순위 큐:
   • 우선순위 큐는 최대 n개의 요소를 저장할 수 있으므로, 공간 복잡도는 O(n)입니다.
2. 기타:
   • StringBuilder를 사용하여 출력을 모아서 처리하므로 출력 버퍼 역시 최대 O(n)의 공간을 차지합니다.

알고리즘 및 자료구조

1. 알고리즘:
   • 이 문제는 우선순위 큐(Priority Queue)를 활용한 그리디 알고리즘 문제입니다. 항상 가장 큰 선물을 주어야 하므로, 각 연산에서 가장 큰 값을 빠르게 찾고 제거할 수 있는 자료구조가 필요합니다.
2. 자료구조:
   • PriorityQueue: 최대 힙을 구현하기 위해 사용됩니다. 자바의 기본 PriorityQueue는 최소 힙이지만, *Collections.reverseOrder()를 사용하여 최대 힙으로 동작하게 만듭니다.

결론

이 코드는 최대 힙을 사용하여 아이에게 가장 가치가 큰 선물을 주는 문제를 효율적으로 해결합니다. 시간 복잡도는 O(n log n)으로, 입력 크기가 최대 5000일 때도 충분히 빠르게 동작할 수 있습니다.