[lv2] 디펜스 게임

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

 

그리디 + 이분탐색

 

1. 그리디 접근

m개 라운드의 enemy를 막으려고 시도할 때,

 

k(무적권)는 항상 enemy[0~m-1] 중

 

상위(enemy 값이 큰) k개의 라운드에 사용한다.

 

=> 우선순위 큐 사용

 

2. 이분 탐색

탐색 범위를 특정할 수 있고, 가능한 원소(answer)중 최대 값을 찾아야 하므로(범위를 확정적으로 좁힐 수 있으므로) 적용 가능하다.

 

=> 상위 k 개를 제외한 원소의 합 midVal을 n과 비교하며 이분 탐색을 진행한다.

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        int st = 0;
        int ed = enemy.length;
        long N = (long) n;
        while(st <= ed) {
            int mid = (st + ed) >>> 1;

            // 최대 100만 * 100만- int 범위 초과
             long midVal = 0;

            PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

            // pq에 일단 다 넣음
            for(int i=0; i<mid; i++) {
                pq.offer(enemy[i]);
            }

            int remain = k;

            // 가장 큰 원소 k개를 뺌
            while(!pq.isEmpty() && remain > 0) {
                pq.poll();
                remain--;
            }

            // midVal : k개를 빼고 남은 원소의 합
            Iterator<Integer> it = pq.iterator();

            while(it.hasNext()) {
                midVal += it.next();
            }

            // midVal이 n 이하면 정답 후보
            if(midVal <= N) {
                answer = Math.max(answer, mid);
                st = mid + 1;
            }
            else ed = mid - 1;
        }

        return answer;
    }
}