[알고리즘] 해를 구하는 최적의 방법을 떠올리기 (레벨2 디펜스 게임)

문제

기록

1. 첫인상은 스택 & 그리디 문제. (들어온 가장 큰것에만 무적권을 쓰는)
2. 그러나 원하는 최대값을 선언적으로 알 수 없음. 다음 스테이지에 뭐가 나올지 미리 알기 어렵기 때문.
3. 해결할 방법은. 가능한 만큼 미션을 클리어 한 후 타임머신을 타고 돌아가, 기억속에 병사 소모가 가장 컸던 것들 먼저 무적권을 사용하는 방법.
4. 그러기 위해선 클리어했던 리스트들을, 가장 큰 순서대로 저장 될 수 있는 리스트를 만들어야함.
5. 결과적으로 우선순위 큐인 힙구조를 만들어야함.
6. 최소힙과 최대힙중 선택적으로 무적권을 사용하기 위해 최대힙을 선택. 해당 문제에 최소힙보다 효율적.
7. 최대힙에 n합만큼 순회하며 추가후 n을 초과하여 힙에 추가하지 못할때 (클리어를 다 했다고 쳤을때) 무적권을 사용해야한다.
8. 그렇다면 무적권을 단순히 내가 클리어한 것중 가장큰것부터 제거하는데 쓰면 되는 것인가?
9. 여기서 무적권을 사용하여 일어날 수 있는 결과는 두가지이다.
   첫째로, 클리어한 것 안에서 무적권 사용후 부활한 병사들을 이용하여 다음 미션을 클리어.
   둘째로, 다음미션에 그냥 바로 무적권을 사용하여 클리어.
10. 그럼 가장 이득을 취하는 방법은 단순히 둘중 비교후 큰거에 무적권을 쓰면 된다.

내 풀이

class MaxHeap {
    constructor(){
        this.heap = [null];
        this.sum = 0;
        this.length = 0;
    }

    push(value){
        this.heap.push(value);
        let current = this.heap.length-1;
        let parent = Math.floor(current / 2);

        while(parent !== 0 && this.heap[parent] < value){
            const temp = this.heap[parent];
            this.heap[parent] = value;
            this.heap[current] = temp;

            current = parent;
            parent = Math.floor(current / 2);
        }
        this.sum += value;
        this.length += 1;
    }
    pop(){
        if(this.heap.length === 2) return this.heap.pop();  

        const returnValue = this.heap[1];
        this.heap[1] = this.heap.pop();

        let current = 1;
        let left = 2;
        let right = 3;

        while(
        this.heap[current] < this.heap[left] || this.heap[current] < this.heap[right]
        ){
            if(this.heap[left] < this.heap[right]){
                const temp = this.heap[current];
                this.heap[current] = this.heap[right];
                this.heap[right] = temp;
                current = right
            } else {
                const temp = this.heap[current];
                this.heap[current] = this.heap[left];
                this.heap[left] = temp ;
                current = left;
            }

            left = current * 2;
            right = current * 2 + 1;
        }
        this.sum -= returnValue;
        this.length -= 1;
        return returnValue;
    }
};


function solution(n, k, enemy) {
    let count = 0;

    const heap = new MaxHeap();  

    for(const e of enemy){
        if(heap.sum + e <= n){
            heap.push(e);
        } else {
            if(k === 0) return heap.length + count;

            const value = heap.heap[1] === undefined ? 0 : heap.heap[1];

            if(value <= e) {
                k -= 1, count += 1;
                continue;
            } else {
                k -= 1, count += 1;
                heap.pop();
                heap.push(e);
            };
        };
    };
    return count + heap.length;
};

파라메트릭 서치?

파라메트릭 서치로도 가능할까 싶었던 문제지만 시도를 하지 않았었는데, 파라메트릭서치로 푼 분들이 있었다.
방법은 파라메트릭 서치로 mid만큼 자르기 => 매번 내림차순으로 검사 => k만큼 클리어 했다 생각하고 나머지 합을 검사. => 만족하는 최소의 조건을 찾을때까지 검사.

물론 효율성적인 측면에서는 아슬아슬하지만, (매 탐색마다 정렬과 합계를 위한 시간복잡도가 요구된다) 흥미로운 풀이인 것 같아서 참고했다.

const check = (n, k, mid, enemy) => {
    if (mid <= k) return true;

    let t = enemy.slice(0, mid).sort((a, b) => b - a);
    let sum = 0;

    for (let i = k; i < t.length; i++) {
        sum += t[i];
        if (sum > n) return false;
    }
    return true;
}

function solution(n, k, enemy) {
    let left = 0, right = enemy.length;

    while(left <= right) {
        let mid = Math.floor((left+right) / 2);
        if(check(n, k, mid, enemy)) left = mid+1;
        else right = mid - 1;
    }

    return left - 1;
}