[프로그래머스] 디펜스 게임 / 자바(Java)

문제

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

프로그래머스

 

---

해설

dfs, dp등 여러 방법을 고려해봤지만 각 변수(n, k, enemy의 길이)가 너무 길어 시간초과가 걸렸습니다.

적들을 만나는데 순서가 있어 정렬을 사용하지 못하겠다고 생각했지만 조금 바꿔보면 가능했습니다.

처음부터 모든 적을 무적권없이 해결한다 가정하고 한계가 올 때마다 그동안 만난 적 중 가장 힘든 적(자동으로 계산하기 위해 우선순위큐를 사용)을 무적권으로 넘겨 다시 병사를 회복한다는 방식으로 해결가능했습니다.

---

코드

import java.util.*;
class Solution {
    int answer;
    public int solution(int n, int k, int[] enemy) {
        answer = 0;
        // 내림차순 정렬
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); 
        
        for(int i=0;i<enemy.length;i++){
            // 무적권이 없으면서 병사도 부족한 경우
            if(n<enemy[i] && k==0) break;
            // 가장 많은 적이 나오는 순으로 나올 수 있도록 출력
            pq.offer(enemy[i]);
            
            // 병사가 부족한 경우 무적권을 사용해 가장 많은 적이 나왔던 라운드를 넘김(병사 회복)
            if(n<enemy[i]){
                n+=pq.poll();
                k--;
            }
            // 현재 라운드의 적 만큼 병사 감소
            n-= enemy[i];
            
            //라운드 진행
            answer++;
        }
        return answer;
    }
}