디펜스 게임

문제

풀이

이 문제를 풀기 위해서는 어떻게 적절한 타이밍에 무적권을 사용할 것이냐? 를 생각해야 한다.

내가 생각한 방법은 무적권을 사용하지 않은 것처럼 계속 라운드를 진행하다가 공격을 막을 수 없게 되는 타이밍에 현재까지 진행한 라운드에서 가장 많은 적이 왔던 라운드에 무적권을 썼던 것처럼 계산하는 방식이다.

처음에는 지금까지 진행한 라운드의 에너미 숫자를 따로 저장하고 무적권을 써야할 때마다 에너미 숫자 순으로 배열을 정렬하여 큰 수를 판별하려 했는데 이 방식을 사용하니 쓸데없이 많은 정렬을 필요로 하여 시간초과가 일어나고 말았다.

어떻게 해야 시간초과가 나지 않으면서 정렬을 할 수 있을까 찾다보니 Priority Queue를 사용하면 되겠다는 결론에 도달했다.

import java.util.*;
class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        int round = enemy.length;
        //큐에 enemy가 큰 순서대로 정렬
        Queue<Integer> enemyQue = new PriorityQueue<>(Collections.reverseOrder());
        int sum = 0;
        
        //무적권이 라운드 수 보다 많을때
        if(k>=round) return round;
        
        //라운드가 진행될 때마다 큐에 enemy를 넣으며 무적권을 써야할때마다 큐에서 가장 큰 숫자를 뺴주며 무적권 사용
        for(int i=0; i<round; i++){
            enemyQue.add(enemy[i]);
            sum += enemy[i];
            if(sum>n){
                if(k>0){
                    k--; 
                    sum -= enemyQue.poll();
                }else{
                    answer = i;
                    break;
                }
            }

            answer=i+1;
            
        }
        
        return answer;
    }
}

우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 것부터 먼저 나오는 큐이다.

여기서는 Collections.reverseOrder()를 써서 값이 큰 것부터 먼저 나오도록 설정하여 정렬하는 시간을 최소화하고 문제를 해결하는데 성공했다.