Leetcode 2542. Maximum Subsequence Score

문제

You are given two 0-indexed integer arrays nums1 and nums2 of equal length n and a positive integer k. 
You must choose a subsequence of indices from nums1 of length k.

For chosen indices i0, i1, ..., ik - 1, 
your score is defined as:

The sum of the selected elements from nums1 multiplied with the minimum of the selected elements from nums2.

It can defined simply as: (nums1[i0] + nums1[i1] +...+ nums1[ik - 1]) * min(nums2[i0] , nums2[i1], ... ,nums2[ik - 1]).

Return the maximum possible score.

A subsequence of indices of an array is a set that can be derived from the set {0, 1, ..., n-1} 
by deleting some or no elements.

n 길이의 배열 두개가 주어질때 0~n-1 의 index중 k개의 조합을 선택했을때
sum(nums1[i_0], nums1[i_1], ..., nums1[i_k-1]) * min(nums2[i_0], nums2[i_1], ..., nums2[i_k-1]) 의 최대값을 구하시오

예시

Input: nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3
Output: 12
Explanation: 
- (1, 3, 2) <-> (2, 3, 4) 로 선택시 12가 된다.

제한

• $1 <= k <= n <= 10^5$
• $n == nums1.length == nums2.length$

풀이법

1. 먼저 nums1 과 nums2를 페어로 만든 뒤 생긴 리스트를 nums2를 기준으로 내림차순 정렬한다.
   

• 이를 통해 위 값을 왼쪽에서 오른쪽으로 순회하면 자연스럽게 nums2 의 최솟값만을 찾을수 있다.

2. 이 후 nums1 에서 선택하는 쌍들의 합이 최대가 되게 하면 된다.

• minheap을 만들고 거기에 nums1을 채운다. 그리고 동시에 n1의 합의 값 또한 더해나간다.
  만약 minheap의 크기가 k가 된다면, 일단 쌍이 완성되었기에 값을 계산하고 minheap에 계속 추가해 나가는데
  minheap의 크기가 k를 넘게 된다면 여기서 값 하나를 pop하고, pop한 값을 n1의 합을 구한것에 빼주면
  계속 최대한의 k개의 nums1의 합을 구할수 있다. 이후 이를 이용 최댓값을 갱신해주면 된다.

from sortedcontainers import SortedList

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        num_pair = list(reversed(SortedList([(nums1[i], nums2[i]) for i in range(len(nums1))], key=lambda a: a[1])))

        sum_ans = 0
        heap = []
        n1_sum = 0

        for one, two in num_pair:
            n1_sum += one
            heapq.heappush(heap, one)
            if len(heap) > k:
                n1_sum -= heapq.heappop(heap)
            if len(heap) == k:
                sum_ans = max(sum_ans, n1_sum * two)

        return sum_ans
        

• SortedList 를 사용했다.