[프로그래머스] 디펜스 게임 - LV 2

📝 문제

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

프로그래머스

🔑 풀이

import java.util.*;

class Solution {
        public int solution(int n, int k, int[] enemy) {
            int answer = 0;

            // PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // 내림차순
            PriorityQueue<Integer> pq = new PriorityQueue<>();

            for (int e : enemy) {
                pq.add(-e); // 내림차순

                // 무적권을 사용하는 상황
                if (k > 0 && n < e) {
                    n += pq.poll() * -1;
                    k--; // 무적권 사용횟수 차감
                }
                n -= e;
                if (n < 0) {
                    break;
                }
                answer++;
            }

            return answer;
        }
    }

 

우선순위 큐를 활용하여 해결

내림차순을 이용하는 경우, Collections.reverseOrder()가 생각 안 날 때 -1을 곱해서 큐에 담은 뒤에 -1을 곱해서 꺼내기

 

 

🔑 다른 풀이

 

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        if(k == enemy.length) return k;
        
        int ans = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int e : enemy){
            if(k > 0){
                k--;
                pq.offer(e);
            }else{
                int num = pq.poll();
                if(num < e){
                    pq.offer(e);
                    n-=num;
                }else{
                    n-=e;
                    pq.offer(num);
                }
                if(n < 0) break;
            }
            
            ans++;            
        }
        
        return ans;
    }
}