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

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

프로그래머스

 

배열의 요소들을 순서대로 n에 마이너스 연산을 한다.

그러다가 n이 0보다 적어지는 순간! 무적권 발동~~

그런데 무적권은 적어지는 순간 그 라운드에 써야할까?

아니다 최대한 많은 라운드를 격파해야 함으로 싸워왔던 라운드 중 가장 큰 수의 라운드에서 써야한다.

그렇다면 매 라운드 병사의 수를 PriorityQueue에 넣고(오름차순 우선) 무적권 발동 시 poll하여 n에 더해주기만 하면 될 것이다. 

 

import java.util.PriorityQueue;

class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.solution(7, 3, new int[] { 4, 2, 4, 5, 3, 3, 1 }));
    }

    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
        for (int i = 0; i < enemy.length; i++) {
            pq.offer(enemy[i]);
            n -= enemy[i];
            if (n < 0) {
                if (k > 0) {
                    k--;
                    n += pq.poll();
                } else
                    break;
            }

            answer++;

        }
        return answer;
    }
}