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

프로그래머스 : 디펜스 게임 (Java)

문제

링크 확인

풀이

처음 가지고 있는 병사 수 n, 무적권의 수 k, 라운드마다 등장하는 적의 수를 담은 1차원 배열 enemy가 주어진다.
i번째 라운드의 적의 수 enemy[i]를 막으려면 n개의 가지고 있는 병사(목숨)에서 enemy[i] 만큼을 차감하고, 차감한 후의 n값이 0 이상이어야 해당 라운드를 통과한 것으로 본다.

간단하게 로직을 구상해보자.

1. 남은 병사 수 remain을 선언한다. 초기값은 n 값과 같다.
2. 최대 enemy 배열 길이만큼 아래 내용을 반복한다.
3. (현재 i번째 반복) remain에서 enemy[i]를 빼준다.
4. 조건을 만족하는 한가지를 진행한다.
   • 만약 enemy[i]를 뺀 remain이 0보다 작다면 라운드를 통과할 수 없다. remain이 0보다 크도록 무적권을 사용하여 넘겨야 한다. 남은 무적권이 없다면 반복을 종료한다.
   • 만약 enemy[i]를 뺀 remain이 0보다 크다면 라운드를 통과한다.
5. 반복한 횟수 i가 통과한 라운드 수 이다.

그럼 4번 과정에서 enemy[i]를 뺀 remain이 0보다 작을 때, remain이 0보다 크도록 무적권을 사용해야 하는데 어떤 라운드에 무적권을 쓰도록 하는 것이 좋을까?
현재까지 진행한 라운드 중 가장 많은 수의 적이 포함된 라운드에 무적권을 사용하는 것이 가장 좋을 것이다.

그럼 어떻게 하면 현재까지 진행한 라운드 중 가장 많은 수의 적이 포함된 라운드를 찾을 수 있을까?
사실 우리는 몇번째 라운드에 무적권을 사용할 지 몰라도 된다.
단지 무적권을 사용할 라운드에 몇 개의 목숨을 지킬 수 있을지(적의 수가 몇인지)만 알면 된다.

우선순위 큐를 사용하면 이 값을 쉽게 찾을 수 있다.
우선순위 큐를 최대힙으로 구성하면 가장 큰 값이 가장 먼저 나오게 된다.
따라서 최대힙으로 구성된 우선순위 큐에 매 라운드 적의 수(enemy[i])를 집어 넣고, 남은 목숨 개수(remain)에서 enemy[i]를 빼준다.
enemy[i]를 뺀 remain 값이 0보다 작다면, 우선순위 큐에서 가장 큰 값을 꺼내어 무적권 사용 처리를 해주면 된다.

코드

Java로 작성한 전체 코드는 다음과 같다.

import java.util.*;

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

        if (k == enemy.length) {
            return enemy.length;
        }

        int count = 0;
        int remain = n;
        int i;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> -(o1 - o2));
        for (i = 0; i < enemy.length; i++) {
            int current = enemy[i];
            priorityQueue.add(current);
            remain -= current;

            if (remain < 0) {
                if (count < k) {
                    remain += priorityQueue.poll();
                    count++;
                } else {
                    break;
                }
            }
        }

        answer = i;

        return answer;
    }
}