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

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

프로그래머스

 

접근 방법

1. 데이터 범위가 n이 10억 이하, k가 50만 이하, enemy배열의 길이가 100만 이하 이다.
2. 따라서 enemy배열을 O(n^2)미만의 알고리즘으로 순회하며 답을 찾아야한다
3. 이전 공격을 저장했다가 가장 낮은 데미지의 공격과 현재 공격을 비교해가며 답을 찾았다.
   1. 우선 k의 수만큼 pq(== 무적권 스킬을 쓸 라운드의 공격력들)에 담는다
   2. 가장 낮은 공격력과 현재 공격력을 비교한다
   3. 현재 공격력이 높다면 이걸 무적권을 써야하므로 pq에 넣는다
   4. 아니라면 현재 공격력을 뺀다
   5. n이 0 보다 작아진다면 이번 라운드를 막지 못하므로 종료

코드

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        if(k == enemy.length) return k;
        
        int ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int e : enemy){
            if(k > 0){
                k--;
                pq.offer(e);
            }else{
                int num = pq.poll();
                if(num < e){
                    pq.offer(e);
                    n-=num;
                }else{
                    n-=e;
                    pq.offer(num);
                }
                if(n < 0) break;
            }
            
            ans++;            
        }
        
        return ans;
    }
}