프로그래머스 - 디펜스 게임

프로그래머스 - 디펜스 게임

디펜스를 위한 병사 규모 n, 공격을 한 라운드 흘릴 수 있는 찬스(=무적권) 횟수 k, 그리고 i번째 라운드의 공격규모를 i번째 원소로 갖는 배열이 주어질 때, 몇 라운드까지 디펜스 할 수 있는지 구하는 문제입니다.
priority queue를 이용했습니다. 규모가 큰 공격에 무적권을 써야 하니까, enemy를 읽어가며 queue에다가 enemy의 가장 큰 원소들 k개를 유지할 것입니다. 또한 동시에 enemy의 부분합인 partialSum과 queue의 원소의 합인 pqSum을 갱신할건데, queue의 원소들에는 무적권을 쓰기로 했으니까 partialSum - pqSum 이 n보다 커지면 디펜스에 실패한 시점이 됩니다. 그러나.....

* 하단에 더 간결한 방법이 있습니다.

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        if (k >= enemy.length) {
            return enemy.length;
        }
        
        int partialSum = 0;
        int pqSum = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // queue에 우선 k개 넣어둠
        for (int i = 0; i < k; i++) {
            pq.add(enemy[i]);
            partialSum += enemy[i];
            pqSum += enemy[i];
        }
        
        for (int i = k; i < enemy.length; i++) {
            partialSum += enemy[i];
            
            // queue의 원소들을 현재까지 가장 큰 원소들 k개로 유지
            if (pq.peek() < enemy[i]) {
                pqSum -= pq.poll();
                pq.add(enemy[i]);
                pqSum += enemy[i];
            }
            
            if (partialSum - pqSum > n) {
                return i;
            }
        }
        
        return enemy.length;
    }
}

 

다른 분의 풀이를 가져왔습니다. 로직은 이렇습니다.

answer번째 라운드의 enemy인 e를 queue에 넣습니다.
n에서 e를 뺍니다 (방어합니다)
n이 0보다 작아지면 (방어 실패) 남은 무적권이 있나 확인합니다. (없으면 끝)
queue에서 제일 큰 원소를 뽑아 여기다가 무적권을 씁니다. (n 회복)

greedy하게 무적권을 쓸 수 있는 이유?
enemy 뒤쪽에 아직 queue에 없는 더 큰 원소가 나올지라도, 이미 앞에서 무적권을 다 쓰면서도 방어 실패한다면 뒤까지 도달하지도 못하기 때문입니다. n을 많이 남기는 게 유리한 게임이 아니고 단지 몇 라운드까지 갈 수 있는지만 구하면 되기 때문이죠.

import java.util.*;

class Solution {
    public int solution(int n, int k, int[] enemy) {
        int answer = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

        for (int e : enemy) {
            queue.add(e);
            answer++;
            n -= e;
            if (n < 0) {
                if(k==0){
                    return answer-1;
                }
                n = n + queue.poll();
                k--;
            }
        }

        return enemy.length;
    }
}