[프로그래머스] 디펜스게임 자바 (level2) (우선순위 큐 maxHeap)

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/142085

문제

• 주어진 내 병력수 n
• 무적스킬 남은 횟수 k
• 라운드 별 적 숫자 enemy
• 주어진 병력과 무적스킬을 활용해서 버틸 수 있는 최대 라운드를 구하는 문제

접근

• 언제 무적스킬을 쓰는게 효율적인지 찾는 DFS방식으로 풀어보고자 함
  • 그러나 굳이 그럴 필요 없이 적의 수가 많은 라운드에 사용하는 것이 효율적임
  → 내림차순 정렬한 우선순위 큐를 사용해서 무적스킬을 사용할 라운드를 정리

/**
     *
     * @param n 내 병력 수
     * @param k 무적스킬 남은 횟수
     * @param enemy 매 라운드별 적의 숫자
     * @return 게임 종료 라운드
     */
    public int solution(int n, int k, int[] enemy) {
        //우선순위 큐 내림차순 정렬
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순으로 정렬된 우선순위 큐
				
        for(int i = 0; i < enemy.length; i ++){
            n -= enemy[i]; //적 숫자만큼 차감
            maxHeap.add(enemy[i]); //큐에 기록
						
						//남은 병력 < 현재 라운드 적
            if(n < 0) {
                if(k > 0 && !maxHeap.isEmpty()){
		                //무적스킬로 가장 적이 많은 라운드 스킵처리 & 병력 회복
                    n += maxHeap.poll(); //내림차순 정렬이므로 가장 큰 값이 나옴
                    k --; //무적스킬 차감
                } else {
                    return i; // 최종 생존 라운드
                }
            }
        }
        return enemy.length; // 최후까지 클리어
    }

알게된 점

• 우선순위 큐 내침차순 정렬로 생성하기
• PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
• 내림차순 설정의 우선순위 큐는 poll을 하면 가장 큰 값부터 나옴.
  • 오름차순의 우선순위 큐의 poll ⇒ 가장 작은 값부터 나옴.