[프로그래머스] 디펜스 게임 (Java) — 우선순위 큐

📌 핵심 요약

• 무적권은 소급 적용이 가능하다 — "언제 쓸지" 미리 결정하지 말고, 병사가 부족해진 순간 지금까지 가장 병사를 많이 쓴 라운드에 쓴 셈 치면 된다.
• 최대 힙(PriorityQueue)으로 최댓값 관리 — 매 라운드 적의 수를 힙에 넣어두면, 소급 적용할 최적의 라운드를 poll() 한 번(O(log N))으로 찾을 수 있다.
• 검증 후 카운트 — answer++는 그 라운드를 실제로 막아냈다는 검증이 끝난 뒤에 실행해야 실패한 라운드가 세어지지 않는다.

 

목차

1 문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/142085

Programmers #142085

디펜스 게임

n ≤ 10⁹ · k ≤ 500,000 · enemy ≤ 1,000,000

난이도: Lv.2

병사 n명으로 매 라운드 enemy[i]마리의 적을 막는 게임이다. 적을 막으면 그 수만큼 병사가 소모되고, 남은 병사보다 적이 많으면 게임이 끝난다. 단, 무적권을 쓰면 병사 소모 없이 한 라운드를 막을 수 있고 최대 k번 사용할 수 있다. 무적권을 최적으로 사용했을 때 최대 몇 라운드까지 버틸 수 있는지 구하는 문제다.

입출력 예

1. n=7, k=3, enemy=[4,2,4,5,3,3,1] → 적이 많은 4, 5, 4 라운드에 무적권을 쓰고 나머지를 병사로 막으면 5라운드까지 버틴다.
2. n=2, k=4, enemy=[3,3,3,3] → 병사로는 한 라운드도 못 막지만 무적권 4번으로 4라운드(전부) 막는다.

2 문제 해결 전략

처음 든 생각: 언제 무적권을 써야 하지?

"적이 많은 라운드에 무적권을 아껴 써야 한다"는 건 직관적으로 알겠는데, 문제는 미래의 적 규모를 모른 채로 현재 라운드에서 결정해야 한다는 점이다. 지금 라운드에 무적권을 썼는데 뒤에 더 큰 적이 나오면 손해다. 그렇다고 모든 경우를 탐색하자니 enemy 길이가 최대 100만이라 완전탐색은 불가능하다.

발상의 전환: 무적권을 소급 적용하자

여기서 관점을 바꾸면 문제가 풀린다. 무적권을 미리 결정할 필요가 없다. 일단 모든 라운드를 병사로 막았다고 치고 진행하다가, 병사가 부족해지는 순간(n < 0)에 "지금까지 지나온 라운드 중 병사를 가장 많이 소모한 라운드에 사실은 무적권을 썼던 걸로" 정정하면 된다. 그 라운드에 썼던 병사(enemy 최댓값)를 돌려받는 것이다.

이 소급 적용이 항상 최적인 이유는 간단하다. 무적권 한 장이 아껴주는 병사 수는 그 라운드의 적 수와 같으므로, 같은 한 장이라면 무조건 적이 가장 많았던 라운드에 쓰는 것이 이득이기 때문이다. 이것이 이 문제의 그리디 논리다.

ℹ️

왜 최대 힙인가?

"지금까지 지나온 라운드 중 최댓값"을 매번 꺼내야 하는데, 배열에서 매번 최댓값을 찾으면 O(N)이라 전체 O(N²)이 된다. 최대 힙은 삽입과 최댓값 추출이 모두 O(log N)이므로, "동적으로 원소가 추가되는 집합에서 반복적으로 최댓값을 뽑는" 이 문제에 정확히 들어맞는 자료구조다.

3 구체적인 구현 단계

① 최대 힙 생성

Java의 PriorityQueue는 기본이 최소 힙이므로, Collections.reverseOrder()를 생성자에 넘겨 최대 힙으로 만든다.

② 일단 병사로 막으며 진행

매 라운드 적의 수를 힙에 넣고(pq.add(e)), 병사에서 차감한다(n -= e). 이 시점의 n은 "무적권 없이 여기까지 왔다면 남았을 병사 수"를 의미한다. 음수가 아니라면 그 라운드는 무사히 방어한 것이다.

③ 병사가 부족하면 무적권 소급 적용

n < 0이 되는 순간이 결정의 순간이다. 무적권이 남아 있다면(k > 0) 힙에서 최댓값을 꺼내 병사를 돌려받고(n += pq.poll()) k를 차감한다. 방금 넣은 현재 라운드의 적도 힙에 들어 있으므로, 현재 라운드가 역대 최대라면 자연스럽게 현재 라운드에 무적권을 쓰는 셈이 된다. 무적권이 없다면 이 라운드는 막을 수 없으니 break로 종료한다.

💡

복구 후 n은 항상 0 이상이 되는 이유

힙에서 꺼낸 최댓값은 방금 차감한 현재 라운드의 적 수(e) 이상이다. 직전까지 n ≥ 0이었으므로, n - e + (최댓값 ≥ e)는 반드시 0 이상으로 회복된다. 즉 무적권이 남아 있는 한 단 한 번의 poll로 그 라운드 방어가 보장되고, while로 반복해서 꺼낼 필요가 없다.

④ 검증이 끝난 뒤 answer++

라운드 방어 성공 여부가 확정된 뒤에야 answer++를 실행한다. 무적권으로 복구했든 병사로 막았든 여기 도달했다면 방어 성공이고, 실패 시에는 break로 빠져나가므로 카운트되지 않는다.

⚠️

answer 갱신 타이밍 주의

answer++를 루프 시작 부분(검증 전)에 두면, 무적권도 없고 병사도 부족해서 막지 못한 마지막 라운드까지 세어버리는 오프바이원 오류가 난다. "조건 검증이 모두 끝난 뒤에 확정한다"는 원칙은 이런 시뮬레이션형 문제에서 특히 자주 시험대에 오른다.

4 전체 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;

        // 최대 힙: 지나온 라운드 중 가장 큰 적 규모를 O(log N)에 조회
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int e : enemy) {
            pq.add(e);  // 현재 라운드도 무적권 후보에 포함
            n -= e;    // 일단 병사로 막았다고 가정

            if (n < 0) { // 병사 부족 → 결정의 순간
                if (k > 0 && !pq.isEmpty()) {
                    // 가장 컸던 라운드에 무적권을 소급 적용 → 병사 회수
                    n += pq.poll();
                    k--;
                } else {
                    break; // 무적권 소진 → 이 라운드는 못 막음
                }
            }

            answer++; // 검증이 끝난 뒤에만 라운드 카운트
        }

        return answer;
    }
}

시간복잡도는 라운드마다 힙 연산이 O(log N)이므로 전체 O(N log N). enemy 길이가 최대 100만이어도 여유 있게 통과한다.

5 정리

단계	핵심 처리	놓치면 생기는 문제	중요도
힙 구성	Collections.reverseOrder()로 최대 힙 생성	기본 최소 힙이면 가장 작은 라운드에 무적권 낭비	필수
진행 순서	힙 삽입 → 차감 → 부족 시 복구	현재 라운드를 힙에 안 넣으면 현재가 최대인 경우 누락	필수
소급 적용	n < 0일 때 최댓값 poll로 병사 회수	미리 무적권 시점을 정하려 하면 그리디 성립 불가	핵심 발상
카운트 시점	검증 완료 후 answer++	못 막은 라운드까지 세는 오프바이원 오류	함정

💡

이 문제에서 배운 것

그리디에서 "언제 쓸까"를 미리 결정하기 어렵다면, 일단 진행하고 한계에 부딪힌 순간 과거의 선택을 정정하는 소급 적용이 강력한 패턴이 된다. 그리고 "동적으로 추가되는 값들 중 최댓값/최솟값을 반복해서 꺼내는" 작업이 보이면 우선순위 큐가 정답 자료구조다. 힙과 그리디는 이렇게 자주 한 세트로 움직인다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.