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

문제 링크

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

문제 설명

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

• 준호는 처음에 병사 n명을 가지고 있습니다.

• 매 라운드마다 enemy[i]마리의 적이 등장합니다.

• 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
  예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
  남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.

• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.

• 무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

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

제한사항

알고리즘: 우선순위 큐

풀이

우리는 최대한 많은 라운드를 진행하는 게 목표다. 그렇게 하려면 무적권이라는 스킬을 최대한 적의 수가 많을 때 사용해야 한다. 즉 적의 수가 적으면 무적권을 아끼고 적의 수가 많으면 무적권을 써야 한다. 그러면 적의 수가 적은지 많은지 판단하는 게 문제인데, 이러한 고민은 우선순위 큐를 사용하면 쉽게 해결된다. 먼저 priorityQueue에 k개만큼 담는다. (오름차순) 그 이후부터는 priorityQueue에 첫 번째 값과 현재 라운드에 적의 수와 비교를 한다. 적의 수가 같거나 적다면 (n -= 적의 수) 해준다. 왜냐하면 우리는 적의 수가 적으면 스킬을 아껴야 되기 때문이다. 적의 수가 더 많다면, 첫 번째 값을 poll()하고 해당 라운드가 priorityQueue에 들어가야 한다. 왜냐하면 우리의 목표는 적의 수가 많을 때 무적권 스킬을 쓰는 게 목표이기 때문이다. 그리고 poll()에 반환값은 n에서 빼준다. 이런 식으로 n값이 음수가 될 때까지 반복한다. (n값이 음수라는 의미는 게임의 종료를 뜻함)

n값이 음수일 때 priorityQueue에는 최대한 많은 라운드를 가기 위해서 스킬을 사용해야 하는 라운드가 들어있게 된다.

소스 코드

import java.util.*;
class Solution {
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        for(int i=0; i<enemy.length; i++) {
            if(priorityQueue.size() < k) {
                priorityQueue.add(enemy[i]);
            } else if(priorityQueue.size() == k){
                if(priorityQueue.peek() < enemy[i]) {
                    n -= priorityQueue.poll();
                    priorityQueue.add(enemy[i]);
                } else n -= enemy[i];
            }
            if(n < 0) break;
            answer += 1;
        }
        return answer;
    }
}