[99클럽 코테 스터디 38일차 TIL] 디펜스 게임 - Java [자바][프로그래머스]

 

📜 문제 내용

 

🤔 과정

• 남아있는 적의 수를 저장하고자 최대힙으로 구현한 PriorityQueue를 이용.
• 기본적으로는 최소힙이지만, 최대힙으로 구현하기 위해 PriorityQueue의 비교자를 (a, b) -> b - a 로 설정.
• 그러면 힙은 큰 값이 먼저 나오게 구성된다.

 

✨ 최초 제출 답안 - 🙆‍♂️ 통과

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        
        // 최대 힙을 구현하기 위해 음수를 저장하는 우선순위 큐 사용
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int totalSum = 0;
        
        for (int i = 0; i < enemy.length; i++) {
            pq.offer(enemy[i]);  // 현재 라운드의 적 수를 큐에 추가
            totalSum += enemy[i]; // 현재 라운드까지의 적 총합
            
            // 병사 수가 부족한 경우
            if (totalSum > n) {
                if (k > 0) {
                    totalSum -= pq.poll(); // 가장 큰 적을 무적권으로 막음
                    k--; // 무적권 사용 횟수 감소
                } else {
                    return i; // 더 이상 막을 수 없는 경우 현재 라운드 반환
                }
            }
        }
        
        // 모든 라운드를 막을 수 있는 경우
        return enemy.length;
    }
}

 

🔗 문제 링크

• 프로그래머스 - 디펜스 게임 (링크) 

프로그래머스