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

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(n, k, enemy) {
    if (enemy.length <= k) {
        return enemy.length;
    }
    
    class PriorityQueue {
        constructor() {
            this.heap = [];
        }
        
        push(value) {
            const heap = this.heap;
            heap.push(value);
            let index = heap.length - 1;
            let parent = Math.floor((index - 1) / 2);
            
            while (index > 0 && heap[index] < heap[parent]) {
                [heap[index], heap[parent]] = [heap[parent], heap[index]];
                index = parent;
                parent = Math.floor((index - 1) / 2);
            }
        }
        
        pop() {
            const heap = this.heap;
            if (heap.length <= 1) {
                return heap.pop();
            }
            
            const output = heap[0];
            heap[0] = heap.pop();
            let index = 0;
            
            while (index * 2 + 1 < heap.length) {
                let left = index * 2 + 1, right = index * 2 + 2, next = index;
                
                if (heap[next] > heap[left]) {
                    next = left;
                }
                
                if (right < heap.length && heap[next] > heap[right]) {
                    next = right;
                }
                
                if (next === index) {
                    break;
                }
                
                [heap[index], heap[next]] = [heap[next], heap[index]];
                index = next;
            }
            
            return output;
        }
    }
    
    let sum = 0;
    const queue = new PriorityQueue();
    enemy.slice(0, k).forEach(v => queue.push(v));
    
    for (let i = k; i < enemy.length; i++) {
        queue.push(enemy[i]);
        const min = queue.pop();
        if (sum + min > n) {
            return i;
        }
        sum += min;
    }
    
    return enemy.length;
}

최대한 많은 라운드를 진행하려면 무적권을 모두 소모하고 남은 라운드의 적의 수를 최소로 만들어야 한다. k번째 라운드까지는 모두 무적권으로 막을 수 있지만, 그 다음부터는 병사들을 소모해야 한다. (k + 1)번째 라운드부터 매번 지금까지의 모든 라운드 중 최소한의 적이 등장하는 라운드만을 골라서 무적권을 사용하지 않고 병사로 막는다면 최대한 많은 라운드를 진행할 수 있다. 그렇다면 (k + 1)번째부터 마지막 라운드까지 하나씩 라운드를 추가하면서 매번 1 ~ (k + 1)번째 라운드 중에 최소한의 적이 등장하는 라운드를 찾아야 하는데, 최소힙을 사용한 우선순위 큐를 구현하면 이 최소한의 적이 등장하는 라운드를 효율적으로 찾을 수 있다.

 

각 라운드별 적의 수를 앞에서부터 순회하면서 우선순위 큐에 추가한다. 이 때 (k + 1)번째 부터는 우선순위 큐에 추가한 다음 최솟값을 큐에서 빼낸다. 큐에서 빼낸 최솟값은 sum에 더하고, 만약 sum이 n보다 크다면 해당 라운드를 진행할 수 없으므로 이전 라운드를 반환한다. 만약 for문을 다 돌았다면 모든 라운드를 진행할 수 있는 것이므로 enemy의 길이를 반환한다.