[프로그래머스] 142085 - 디펜스 게임 (JavaScript)

 

 

아이디어

 

라운드를 돌면서 현재 라운드까지 적이 많이 등장했던 라운드들에서 무적권을 사용한다.

입력 값의 범위가 크므로 힙을 이용하며, 힙에서 최솟값을 삭제하고 큰 값들을 저장하기 위해 최소힙으로 구현한다.

 

 

풀이

 

swap 함수는 배열을 이용하여 두 노드가 서로의 값을 참조하도록 하여 값을 바꾸도록 한다.

heappush 함수는 힙에 노드를 삽입하고, 차례로 부모 노드와 값을 비교하여 최소힙으로 정렬한다.

heappop 함수는 힙의 최솟값인 루트 노드를 힙의 마지막 노드와 자리를 바꾼 뒤 그 값(없으면 0)을 저장해두고 삭제한다.

루트 노드에서부터 차례로 자식 노드들과 값을 비교하여 두 자식 노드 중 값이 가장 작은 노드와 자리를 바꿔 정렬한다.

 

라운드를 돌면서 힙에 큰 값들이 저장되도록 갱신해 나가고, 그 합을 sumHeap에 저장한다.

현재까지 등장한 적의 수 총합 total에서 sumHeap을 뺀 값이 병사 수 n보다 작거나 같은 동안 결과값을 증가시킨다.

 

function solution(n, k, enemy) {
    
    function swap(a, b) {
        [heap[a], heap[b]] = [heap[b], heap[a]];
    }
    
    function heappush(heap, newNode) {
        heap.push(newNode);
        let idx = heap.length-1;
        while (idx > 0) {
            let parentIdx = Math.floor((idx-1)/2);
            if (heap[idx] < heap[parentIdx]) {
                swap(idx, parentIdx);
            }
            idx = parentIdx;
        }
    }
    
    function heappop(heap) {
        let value = 0;
        if (heap.length > 0) {
            swap(0, heap.length-1);
            value = heap.pop();
            
            let idx = 0;
            while (idx*2+1 < heap.length) {
                let childIdx = idx;
                if (heap[idx*2+1] < heap[idx]) childIdx = idx*2+1;
                if (idx*2+2 < heap.length && heap[idx*2+2] < heap[childIdx]) childIdx = idx*2+2;
                if (heap[childIdx] >= heap[idx]) break;
                swap(idx, childIdx);
                idx = childIdx;
            }
        }
        return value;
    }
    
    let heap = [];
    let total = sumHeap = answer = 0;
    for (let i=0; i<enemy.length; i++) {
        if (heap.length < k || enemy[i] > heap[0]) {
            if (heap.length >= k) {
                sumHeap -= heappop(heap);
            }
            heappush(heap, enemy[i]);
            sumHeap += enemy[i];
        }
        total += enemy[i];
        if (total-sumHeap > n) break;
        answer++;
    }
    return answer;
}