[프로그래머스] 디펜스 게임 - Java

문제

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

프로그래머스

 

---

 

문제 개요

디펜스 게임은 준호가 병사 n명으로 적의 공격을 막는 게임입니다. 게임의 규칙은 다음과 같습니다:

1. 병사 소모: 매 라운드마다 enemy[i]마리의 적이 등장하며, 이를 막기 위해 enemy[i]명의 병사가 소모됩니다.
2. 병사 부족 시 게임 종료: 만약 남은 병사 수가 등장한 적의 수보다 적다면 게임은 종료됩니다.
3. 무적권 사용: 무적권을 사용하면 병사를 소모하지 않고 한 라운드를 막을 수 있습니다. 무적권은 최대 k번 사용할 수 있습니다.
4. 목표: 무적권을 적절히 사용하여 최대한 많은 라운드를 진행하는 것입니다.

입력으로는 병사의 초기 수 n, 무적권 사용 횟수 k, 매 라운드마다 등장하는 적의 수 배열 enemy가 주어집니다. 이를 기반으로 준호가 막을 수 있는 최대 라운드 수를 구해야 합니다.

 

접근 방법

1. 우선순위 큐를 활용한 최대 적 병력 추적:
   • 매 라운드 적의 병력을 추적하기 위해 우선순위 큐(Priority Queue)를 사용합니다.
   • 병사가 부족한 상황(n < 0)이 발생하면, 지금까지 마주한 적들 중 가장 큰 병력을 무적권으로 처리하여 병사의 소모를 줄입니다.
2. 병력 감소 및 무적권 사용:
   • 각 라운드에서 n에서 적의 병력(enemy[i])을 차감합니다.
   • 차감 후 병사가 부족할 경우:
     • 무적권(k)이 남아 있다면, 큐에서 가장 큰 병력을 꺼내(poll) 무적권으로 처리하고 병력을 복구합니다.
     • 무적권이 없다면, 더 이상 방어할 수 없으므로 현재 라운드 번호를 반환합니다.
3. 모든 라운드 방어 가능 여부:
   • 모든 라운드를 방어할 수 있는 경우, enemy 배열의 길이를 반환합니다.

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < enemy.length; i++) {
            n -= enemy[i];
            pq.offer(enemy[i]);
            
            if (n < 0) {
                if (k > 0) {
                    n += pq.poll(); // 가장 큰 적의 병력을 복구
                    k--;
                } else {
                    return i; // 더 이상 방어 불가
                }
            }
        }
        return enemy.length; // 모두 방어 가능
    }
}