[programmers/java] 디펜스 - 우선순위큐, PriorityQueue

1. 문제 개요

- url : https://school.programmers.co.kr/learn/courses/30/lessons/142085?language=java

병사 n명을 보유한 사용자가 연속되는 적의 공격을 막는 디펜스 게임이 주어진다. 게임은 라운드마다 등장하는 적의 수만큼 병사를 소모하며, 병사의 수가 부족한 경우 게임이 종료된다. 다만, k회까지 사용할 수 있는 무적권을 통해 병사 소모 없이 적의 공격을 막을 수 있다.

사용자는 무적권을 전략적으로 활용하여 최대한 많은 라운드를 버티는 것이 목표이며, 최종적으로 방어할 수 있는 라운드 수를 반환해야 한다.

---

2. 입력 및 출력 형식

• 입력값:
  • n (int): 초기 병사 수 (1 ≤ n ≤ 1,000,000,000)
  • k (int): 무적권 사용 가능 횟수 (0 ≤ k ≤ 500,000)
  • enemy (int[]): 각 라운드의 적 수를 담은 배열 (1 ≤ enemy.length ≤ 1,000,000, 1 ≤ enemy[i] ≤ 1,000,000)
• 출력값:
  • 사용자가 최대로 버틸 수 있는 라운드 수 (int)

---

3. 해결 전략

무적권은 가장 많은 병사를 소모하는 라운드에 소급 적용하는 것이 이득이다.
게임을 순차적으로 진행하며 병사 수를 감소시키되, 병사가 부족해지는 시점에서는 기존에 가장 많은 병사를 소모했던 라운드 하나를 무적권으로 대체해야 한다.

이를 위해 최대 힙(PriorityQueue) 자료구조를 활용하여, 현재까지 등장한 적 수 중 가장 큰 값을 빠르게 찾아 제거하고 병사 수를 복구하는 방식으로 구현한다.

---

4. Java 구현

import java.util.PriorityQueue;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);  // 최대 힙 선언

        for (int i = 0; i < enemy.length; i++) {
            n -= enemy[i];             // 병사 차감
            maxHeap.offer(enemy[i]);   // 힙에 적 수 기록

            if (n < 0) {
                if (k > 0) {
                    n += maxHeap.poll();  // 무적권 사용: 가장 많은 적 수 복구
                    k--;
                } else {
                    return i;  // 병사도 없고 무적권도 없는 경우, 종료
                }
            }
        }

        return enemy.length;  // 모든 라운드를 방어한 경우
    }
}