디펜스 게임 (프로그래머스) JAVA

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

프로그래머스

 

문제 설명

• 각 라운드 마다 적의 수를 알려줄 때 무적권을 적절하게 잘 사용해서 최대한 많은 라운드를 처리해야 합니다.
• 예를 들어 4,4,5를 무적권을 사용해 처리하고 2,3을 병사로 처리하면 병사는 2명 남습니다. 다음 라운드에 3명의 적이 오므로 라운드를 해결할 수 없으므로 최대 5라운드 까지 처리 가능합니다.

 

문제에 대한 아이디어

제일 처음 생각한 방법은 enemy를 정렬해서 k 번째 큰 숫자 num을 구합니다. 그 후 enemy를 탐색하면서 num 보다 큰 것은 넘어가고 작은 것만 n을 줄여가면서 적을 처리하는 것입니다. 하지만 실행해본 결과 틀리고 시간도 오래걸렸습니다. 

그래서 생각한 방법이 2번째 방법입니다. 계속 제일 큰 숫자를 구해놓고 탐색을 할려 했습니다.  하지만 다르게 생각해서 현재 까지 진행하면서 큰 숫자를 가지고 있으면서 n이 0보다 아래로 내려가면 그 숫자를 더 해주는 것입니다. 그러면 현재까지 진행하면서 제일 큰 숫자에는 무적권을 사용한 것 입니다. 이것을 구현하기 위해 heap을 사용했습니다. 우선순위 큐를 사용했습니다.

 

전체 코드 

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 0; i < enemy.length; ++i){
            maxHeap.add(enemy[i]); // 현재 진행하면서 제일 큰 숫자 
            n -= enemy[i];
            if(n < 0 && k > 0){ // 무적권 사용
                n += maxHeap.poll();
                k--;
                answer = i;
            }
            if(n < 0 && k <= 0) { // 더 이상 진행 불가
                answer = i-1;
                break;
            }
            if(n >= 0) { // 여기 까지는 진행 완료
                answer = i;
            }
        }
        return answer+1;
    }
}