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

문제

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

프로그래머스

 

풀이

n = 병사의 수

k = 무적권의 갯수

enemy [] = 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열

enemy.length = 라운드 개수

 

1. 무적권의 개수 == 라운드의 개수 : 모든 라운드를 막을 수 있다는 뜻으로 라운드의 개수 리턴

2. 무적권의 개수가 라운드의 개수보다 다를 때는 병사를 소모하여 라운드를 막아야한다.

이때, 특정 라운드에 무적권을 써서 최대한 많은 라운드를 진행해야 한다.

따라서 다음과 같이 풀이를 했다.

1) PriorityQueue를 선언 

2 - 1) 라운드를 진행하면서 병사의 수에서 각 라운드의 적의 수 빼기 

2 - 2) answer = 진행한 라운드 수이므로 answer += 1 시행

2 - 3) PriorityQueue에 해당 라운드의 적의 수 넣기

3) 병사의 수가 마이너스일 경우

3 - 1) 무적권의 수가 없으면 answer -= 1

3 - 2) 무적권의 수가 있으면 병사의 수를 복구 -> PriorityQueue에서 가장 큰 적의 수로 => 무적권 수 빼기

코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        if(k == enemy.length) return enemy.length;

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int soldier = n;
        int answer = 0;
        for(int i=0;i<enemy.length;i++){
            soldier -= enemy[i]; 
            answer += 1;
            pq.add(enemy[i]);

            if(soldier < 0){
                if(k == 0) {
                    answer -= 1;
                    break;
                }
                soldier += pq.poll();
                k -= 1;
            }
        }

        return answer;
    }
}