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

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

프로그래머스

코딩테스트 연습 > 연습문제 > 디펜스 게임 

 

문제 접근

우선순위 큐 활용 문제?이다. 

 

우리는 언제 무적권이라는 스킬을 써야 할지 정해야 한다. 

백트래킹을 통해서 모든 경우의 수를 알아내고 적절하게 무적권을 써서 최선의 결과를 알고 싶지만 

제한사항을 보면 데이터 셋이 매우 큰 편임을 알 수 있다. 

이렇게 항상 데이터의 크기를 먼저 보고 백트래킹 적용 가능성을 체크하자.

 

무적권 스킬을 언제 사용할지 못 정하니 다른 방법이 필요하다.

나는 항상 무적권 스킬을 쓰고 만약 무적권을 다 사용했다면(K==0)

지금까지 무적권으로 막은 적의 수를 우선순위 큐(최소힙)를 통해 저장하다가 가장 적게 사용한 값을 나의 실제 병사를 사용해서 라운드를 통과하게 하였다. 

이렇게 구현하면 최대한 많은 라운드를 통과 가능하다.

 

전체 코드

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(); 
        for(int i = 0; i < enemy.length; i++){
            pq.add(enemy[i]);
            if(pq.size() <= k){
                answer++;
                continue;
            }
            n -= pq.poll();
            if(n < 0) break;
            answer++;
        }
        return answer;
    }
}