[LeetCode] 2542. Maximum Subsequence Score, Medium

1. 문제

• 정수 배열 nums1과 nums2가 주어질 때, k개의 인덱스를 선택해서 nums1의 합 * nums2의 최소값이 최대가 되는 값을 구하라.

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 maxScore(nums1: number[], nums2: number[], k: number): number {
    const n = nums1.length;
    const pairs = nums1.map((num, i) => [nums2[i], num]);

    // nums2 기준 내림차순 정렬
    pairs.sort((a, b) => b[0] - a[0]);

    const heap = new MinHeap();
    let sum = 0;
    let max = Number.MIN_SAFE_INTEGER;

    for(let i = 0; i< pairs.length; i++) {
        const [num2, num1] = pairs[i];

        heap.push(num1);
        sum += num1;

        if(heap.size() > k) {
            sum -= heap.pop();
        }

        if(heap.size() === k) {
            max = Math.max(max, num2 * sum);
        }

    }
   
    return max;
}

• 못 풀었다.
• 원리는 nums2는 최솟값을 골라야 하는데, 곱하기 때문에 최솟값 중 최대 값을 골라야 한다.
• nums2, nums1의 값들을 맵핑해서 관리하고, nums2를 내림차순 정렬하여 순서대로 탐색한다.
• 탐색하면서 nums1의 값은 최소 힙에 큰 값을 k개만 유지하도록 한다. 
• k개가 담겼을 때 최대값 갱신.