디펜스 게임 [자바]

 

🧫 문제 분석

✔️ 출처

디펜스 게임 level 2

📖 문제

 

우선순위 큐를 사용한 탐욕법(그리드) 알고리즘 문제이다. 

 

내가 생각한 방법

1 ~ k번째까지는 무적권을 사용한다 가정하고 우선순위 큐에 넣는다.

이때 최댓값을 저장한다. 

 

2가지 경우 무적권 사용 라운드를 바꾼다. 

• 현재 라운드의 적 수 >= 무적권을 사용한 라운드의 최대 적 수 
• 현재 라운드의 적 수 > 무적권을 사용한 라운드의 최소 적 수 

이 두가지를 만족하면서 최소 적수를 n에서 뺐을때 0미만이 안될때 무적권 사용 라운드를 바꾼다.

그리고 최댓값을 갱신한다. 

 

 

위 2가지 경우가 아니라면 

남은 n 명이 현재 라운드 수보다 크거나 같으면 

빼주어 현재 라운드를 막는다.

 

 

---

🔅 문제 풀이

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 우선순위 큐에 일단 k까지 넣는다. 
        // 넣은 값들의 최댓값을 저장
        int answer = 0;
        int max = 0;
        
        for (int i = 0; i < enemy.length; i++) {
            
            // k 까지 우선 넣음
            if (i < k) {
                pq.add(enemy[i]);
                max = Math.max(max, enemy[i]);
                answer++;
                continue;
            }
            
            // 무적권 사용으로 넘어간 적 최대수 보다 현재 라운드 적이 많거나
            // 무적권 사용으로 넘어간 적 최소수 보다 현재 라운드 적이 더 많다면
            if ((max <= enemy[i] || pq.peek() < enemy[i]) && n >= pq.peek()) {
                n -= pq.poll();
                pq.add(enemy[i]);
                answer++;
                
                max = enemy[i]; // 최댓값 갱신
                
                // n명으로 막기
            } else if (n >= enemy[i]){
                n -= enemy[i];
                answer++;
                // 막지 못한 경우 멈춤
            } else {
                break;
            }
        }
        
        
        return answer;
    }
}

 

❗ 오답노트 / 필요한 지식

1. 처음에는 TreeSet을 써봤는데 생각해보니 Set이라 중복 저장이 안된다. 그래서 다시 우선순위 큐로 돌아갔다.
2. pq의 최솟값 < 현재 라운드 적 수 를 생각해내지 못해 좀 고생했다. 질문하기의 모든 반례는 다 통과해버려서 원인을 모르겠는데 곰곰히 생각해보니 해당 case가 있어서 이를 고려했더니 바로 풀렸다.