[Programmers] 디펜스게임.java

# 디펜스 게임

# 이 과정

브루트포스로 모든 경우의 수를 구한다면 쉽게 풀 수 있는 문제겠지만

이 문제에서 주어진 범위가 매우 크다

따라서 브루트포스가 아닌 다른 알고리즘을 사용해야 한다

최대 몇 라운드까지 방어가 가능한지를 구해야 하기 때문에 우선순위 큐를 사용해서 최대로 방어할 때의 값을 출력해주면 된다

 

# 정답 코드

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        // 준호의 처음 병사 수 n
        // 사용 가능한 무적권의 횟수 k
        // 공격 병사 수 배열 enemy
        // 최대 몇라운드까지 방어 가능한지 구하기
        int answer = enemy.length;
        Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i=0; i<enemy.length; i++) {
            n -= enemy[i];
            pq.add(enemy[i]);
            
            if(n < 0) {
                if(k > 0 && !pq.isEmpty()) {
                    n += pq.poll();
                    k--;
                }
                else {
                    answer = i;
                    break;
                }
            }
        }
        return answer;
        
    }
}