[JS] 2Level / 연습문제 / 디펜스 게임

문제 설명

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

프로그래머스

 

문제 풀이 방법

이번 문제는 최소 힙을 적용한 우선순위 큐를 이용해 풀어야 했던 문제이다.

 

나는 정렬을 이용해 웨이브가 가장 큰 순서대로 해결하려 했다.

하지만, 이렇게 하게 되면 초반에 작은 웹이브들의 합이 갖고있는 병사의 수를 넘는 경우는 처리하지 못하기에 포기했다.

 

그렇다면 큰 웨이브는 무적권을 사용한다 치고, 작은 수만 골라 문제를 풀어야 한다는 것이다.

이진 탐색을 통해 웨이브 배열을 처음과 끝부터 시작해 탐색하는 방법도 좋다고 생각했다.

하지만, 문제의 제한사항을 보고 시간복잡도를 생각해 문제를 풀어야한다.

 

그렇다면 최소힙을 이용한 우선순위 큐를 사용하게 되면 O(log(n))으로 삽입과 추출을 할 수 있게 된다.

이를 사용해 문제를 풀어야 겠다.

 

무적권은 게임 진행중에 전부 소진하는 것이기에 초반에 사용했다 치고 무적권의 개수만큼 초반 웨이브를 힙에 추가를 해준다.

최소힙으로 구성된 이진 트리에 웨이브 값들이 들어가면 다음 웨이브 값을 넣어준다.

이후 가장 작은 값을 추출해 남은 병사와 지금까지 (처리한 병사의 합+추출한 값)을 비교해 남은 병사가 많다면 계속, 적다면 현재의 웨이브 숫자를 반환해준다.

 

코드

class PriorityQueue {
    constructor() {
        this.heap = [];
    }
    
    push(value) {
        const heap = this.heap;
        heap.push(value);
        let idx = heap.length - 1;
        let parent = Math.floor((idx - 1) / 2);
        
        while(idx > 0 && heap[parent] > heap[idx]){
            [heap[parent], heap[idx]] = [heap[idx], heap[parent]];
            idx = parent;
            parent = Math.floor((idx - 1) / 2)
        }
    }
    pop() {
        const heap = this.heap;
        if(heap.length <= 1){
            return heap.pop();
        }
        
        const output = heap[0];
        heap[0] = heap.pop();
        let idx = 0;
        
        while(idx * 2 + 1 < heap.length){
            let left = idx * 2 + 1;
            let right = idx * 2 + 2;
            let next = idx;
            
            if(heap[next] > heap[left]){
                next = left;
            }
            if(right < heap.length && heap[next] > heap[right]){
                next = right;
            }
            if(next === idx){
                break;
            }
            [heap[idx], heap[next]] = [heap[next], heap[idx]];
            idx = next;
        }
        return output;
    }
    
}

const solution = (n, k, enemy) => {
    let arr = new PriorityQueue();
    let cap = 0;
    
    enemy.slice(0, k).forEach(e => arr.push(e));
    
    for(let i=k; i<enemy.length; i++){
        arr.push(enemy[i]);
        let popN = arr.pop();
        if(cap + popN > n){
            return i;
        }
        cap += popN;
    }
    return enemy.length;
}