2542. Maximum Subsequence Score

Maximum Subsequence Score - LeetCode

Maximum Subsequence Score - LeetCode

nums1, nums2 주어진 숫자 배열에서 k 개의 index 를 뽑아,

nums1 에서는 총합 / nums2 에서는 가장 작은 수를 곱하여 최종 값이 가장 큰 값을 찾는 문제입니다.

 

처음에는 주어진 배열의 총 길이 ( N ) 에서 combination 을 찾아 가장 큰 수를 찾는 문제로 접근했습니다.

이 경우는 Time Complexity 가 N^(K-1) 로 모든 경우의 수를 판별하기에는 큽니다,

이를 가지치기로 나눠서 접근했고 경우의 수를 줄였지만 Time Limit Exceeded 가 발생합니다.

 

두 번째 접근은 정렬을 통해 MinArray ( 가장 작은 수가 배열의 끝에 위치하는 내림차순으로 정렬된 배열 ) 을 구성하여,

답을 추론했지만 이 경우는 배열을 탐색하는 비용 O ( N ) 과 정렬에 소요되는 비용 O ( N ) 이 발생하여,

O ( N ^ 2 ) 를 요구합니다. 이 비용으로도 Time Limit Exceeded 가 발생합니다. 

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number} k
 * @return {number}
 */
var maxScore = function (nums1, nums2, k) {
    // sort
    var tuple = nums2.map((_, idx) => [nums1[idx], nums2[idx]]);
    tuple.sort((a, b) => b[1] - a[1]);
    for (var i = 0; i < tuple.length; i++) {
        nums1[i] = tuple[i][0];
        nums2[i] = tuple[i][1];
    }

    var len = nums1.length;

    var queue = new Array();
    var sum = 0, answer = 0;

    // O ( N )
    for (var i = 0; i < len; i++) {
        // O ( N )
        var prev = undefined;
        for (var j = 0; j < queue.length; j++) {
            if (prev != undefined) {
                var cache = queue[j];
                queue[j] = prev;
                prev = cache;
            } else if (nums1[queue[j]] < nums1[i]) {
                prev = queue[j];
                queue[j] = i;
            }
        }
        if (prev === undefined) {
            queue.push(i);
        } else {
            queue.push(prev);
        }

        sum += nums1[i];

        // find best score
        if (queue.length == k) {
            var value = sum * nums2[i];
            if (answer < value) answer = value;

            var big = queue.pop();
            sum -= nums1[big];
        }
    }

    return answer;
};

마지막으로는 MinHeap ( Heap - Tree ) 를 구성하여 정렬에 소요되는 비용을 O ( log N ) 으로 줄일 수 있습니다.

* LeetCode ( js ) 에서는 datastructures ( module ) 을 제공하고 있습니다 ( GitHub - datastructures-js/priority-queue: :1234: A heap-based implementation of priority queue )

위 방법으로 최종 O ( N * log N ) 으로 문제를 풀 수 있으며 이 Time Complexity 에서는 해결할 수 있습니다.

* Heap 을 사용하는 문제로 파악되네요

* MinPriorityQueue 는 MinHeap 과 같은 알고리즘을 사용합니다

var maxScore = function(nums1, nums2, k) {
    // Create a reverse sorted array of [nums1(i), nums2(i)]
    const zip = nums1.map((x,i) => [x, nums2[i]]).sort((a,b) => b[1] - a[1]);
    let sum = 0, ans = 0;
    const pq = new MinPriorityQueue(); // Smallest element on top
    
    for(const [n1, n2] of zip) {
        // Insert element of nums1 in queue and also add to sum
        pq.enqueue(n1);
        sum += n1;

        // Now we get subsequence of k elements
        if(pq.size() === k) {
            ans = Math.max(ans, sum*n2); // Update our ans
            // Remove element from queue and also from sum
            sum -= pq.dequeue().element;
        }
    }

    return ans;
};