[LeetCode] 2462. Total Cost to Hire K Workers, Medium

1. 문제

• 각 사람 별 고용 비용을 담은 costs 배열이 주어지고, 사람을 고용하는 횟수 k와 선택할 수 있는 사람 수 candidates가 주어질 때, 최소 비용으로 사람을 고용하라.
• candidates는 costs 배열의 앞과 뒤에서 동시에 선택하여, 최소 비용인 사람을 선택해 고용한다.

2. 해결

class MinHeap {
    private heap: number[];

    constructor() {
        this.heap = [];
    }

    getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
    getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
    getParentIndex = (childIndex) => Math.floor((childIndex - 1) /2);

    swap = (i: number, j: number) => {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    };

    peek = () => this.heap[0];
    size = () => this.heap.length;

    push(value: number) {
        this.heap.push(value);
        this.heapifyUp();
    }

    heapifyUp() {
        let index = this.heap.length - 1; // 마지막 요소.

        while(index > 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) { // 부모 노드보다 자식 노드가 작은 경우.
            this.swap(index, this.getParentIndex(index)); // 스왑.
            index = this.getParentIndex(index);
        }
    }

    pop(): number | undefined {
        if(this.heap.length === 0) return undefined;
        if(this.heap.length === 1) return this.heap.pop();

        const top = this.heap[0];
        this.heap[0] = this.heap.pop(); // 마지막 값을 root로 놓고.
        this.heapifyDown();

        return top;
    }

    heapifyDown() {
        let index = 0;
        
        while(this.getLeftChildIndex(index) < this.heap.length) { // 자식이 있는 경우 반복, left가 없으면 right도 없기 때문에.
            // 왼쪽, 오른쪽 중 더 작은 자식을 찾음. 최소 힙이므로.
            let smallerChildIndex = this.getLeftChildIndex(index);
            const rightChildIndex = this.getRightChildIndex(index);

            if(rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[smallerChildIndex]) {
                smallerChildIndex = rightChildIndex;
            }

            if(this.heap[index] <= this.heap[smallerChildIndex]) break; // 현재 노드가 자식보다 작거나 같으면 종료.

            this.swap(index, smallerChildIndex);
            index = smallerChildIndex;
        }
    }
}

function totalCost(costs: number[], k: number, candidates: number): number {
    const leftHeap = new MinHeap();
    const rightHeap = new MinHeap();

    let totalCost = 0;

    let left = 0, right = costs.length - 1;

    while(left < candidates && left <= right) {
        leftHeap.push(costs[left]);
        left++;
    }

    while(right >= costs.length - candidates && left <= right) {
        rightHeap.push(costs[right]);
        right--;
    }

    while(k > 0) {
        if(leftHeap.size() === 0) totalCost += rightHeap.pop();
        else if(rightHeap.size() === 0) totalCost += leftHeap.pop();
        else {
            if(leftHeap.peek() <= rightHeap.peek()) {
                totalCost += leftHeap.pop();
                if(left <= right) {
                    leftHeap.push(costs[left]);
                    left++;
                }
            } else {
                totalCost += rightHeap.pop();
                if(right >= left) {
                    rightHeap.push(costs[right]);
                    right--;
                }
            }
        }
        k--;
    }

    return totalCost
};

• 처음 보는 문제 유형이라 풀지 못했다.
• 이 문제는 투 포인터 + 최소 힙을 이용해야 한다.
• 투 포인터를 이용해 좌, 우측의 최소 힙을 두고 지원자 수를 앞과 뒤에서 뽑아 담는다.
• 이후 k번 반복하며 두 힙 중 루트가 작은 값을 선택하며 포인터를 이동시킨다. 이때, 같은 값이면 좌측 힙에서 선택해야 함에 주의.