디펜스 게임

Level2

프로그래머스📅 2025-07-11

그리디우선순위 큐

문제 설명

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

준호는 처음에 병사 n명을 가지고 있습니다.
매 라운드마다 enemy[i]마리의 적이 등장합니다.
남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
- 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
- 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다. 준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

1 ≤ n ≤ 1,000,000,000
1 ≤ k ≤ 500,000
1 ≤ enemy의 길이 ≤ 1,000,000
1 ≤ enemy[i] ≤ 1,000,000
enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

입출력 예

입력

n = 7
k = 3
enemy = [4, 2, 4, 5, 3, 3, 1]

출력

설명

1, 3, 5 라운드의 공격을 무적권으로 막아내고, 2, 4 라운드에 각각 병사를 2명, 5명 소모하면 5라운드까지 공격을 막을 수 있습니다. 또, 1, 3, 4번째 공격을 무적권으로 막아내고, 2, 5 번째 공격에 각각 병사를 2명, 3명 소모하여 5라운드까지 공격을 막을 수 있습니다. 그보다 많은 라운드를 막는 방법은 없으므로 5를 return 합니다.

입력

n = 2
k = 4
enemy = [3, 3, 3, 3]

출력

설명

준호는 모든 공격에 무적권을 사용하여 4라운드까지 막을 수 있습니다.

풀이 접근법

시간복잡도 : O(N log k)

공간복잡도 : O(k)

사용 알고리즘 :

그리디우선순위 큐

핵심 포인트 :

무적권은 가장 큰 적의 공격에 사용하는 것이 최적
최소 힙을 사용하여 현재까지 사용한 무적권 중 가장 작은 값을 추적
우선순위 큐 크기가 k를 초과하면 가장 작은 값을 제거하고 병사로 막음

경계값/반례 :

모든 라운드를 막을 수 있는 경우
무적권만으로 모든 라운드를 막을 수 있는 경우

핵심 아이디어

무적권은 가장 큰 적의 공격에 사용하는 것이 최적
매 라운드마다 현재 적을 우선순위 큐에 추가
우선순위 큐 크기가 k를 초과하면 가장 작은 값(최소 힙의 루트)을 제거하고 병사로 막음
병사가 부족하면 그 시점에서 게임 종료

해결 방법

최소 힙(우선순위 큐)을 사용하여 무적권을 사용할 적들을 관리
각 라운드마다 현재 적의 수를 우선순위 큐에 추가
우선순위 큐 크기가 k를 초과하면 가장 작은 값을 제거하고 병사로 막음
병사가 부족하면 현재 라운드에서 게임 종료
모든 라운드를 성공적으로 막으면 전체 라운드 수 반환

핵심 패턴

1️⃣ 무적권 최적 사용 전략

// 무적권을 사용할 적들을 최소 힙으로 관리
PriorityQueue<Integer> pq = new PriorityQueue<>();

// 현재 적을 무적권 후보에 추가
pq.add(enemy[i]);

// k개를 초과하면 가장 작은 값을 병사로 막음
if (pq.size() > k) {
    n -= pq.poll();
}

무적권은 가장 큰 적에게 사용하는 것이 최적
최소 힙으로 무적권 후보를 최대 개수를 유지하며 관리한다.
무적권 후보 개수를 넘어서면 가장 작은 적을 꺼내서 직접 처리

2️⃣ 게임 종료 조건 체크

if (n < 0) {
    return i;  // 현재 라운드 인덱스 반환
}

병사가 부족하면 즉시 게임 종료
Java의 인덱스이므로 i가 곧 최종 막은 라운드 수

3️⃣ 모든 라운드 완료 처리

return enemy.length;

모든 라운드를 성공적으로 막은 경우 전체 길이 반환

제출 코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();  
        
        for (int i = 0; i < enemy.length; i++) {
            pq.add(enemy[i]);
            
            if (pq.size() > k) {
                n -= pq.poll();
                
                if (n < 0) {
                    return i;
                }
            }
        }
        
        return enemy.length;
    }
}