[LeetCode 75] Medium - 2542. Maximum Subsequence Score

2542. Maximum Subsequence Score

 

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        pairs = [(n1, n2) for n1, n2 in zip(nums1, nums2)]
        pairs = sorted(pairs, key=lambda p: p[1], reverse=True)

        minHeap = []
        n1Sum = 0
        res = 0
        for n1, n2 in pairs:
            n1Sum +=n1
            heapq.heappush(minHeap, n1)

            if len(minHeap) > k:
                n1Pop = heapq.heappop(minHeap)
                n1Sum -= n1Pop

            if len(minHeap) == k:
                # nums2를 내림차순으로 정렬했기 때문에, 
                # 현재 처리 중인 n2 값은 정렬된 순서상 가장 작은 값으로 선택됨
                # 따라서, 새로 추가된 n2 값은 
                # 항상 "현재까지 선택된 모든 n2 값 중 가장 작은 값"이 됩니다.
                res = max(res, n1Sum*n2)
        return res

 

여전히 잘 모륵겠음