2023.05.24 Today's Challenge

fabichoi 2023. 5. 24. 23:45

https://leetcode.com/problems/maximum-subsequence-score/

Maximum Subsequence Score - LeetCode

Can you solve this real interview question? 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 indic

leetcode.com

오늘도 힙을 이용해서 푸는 문제

class Solution:
    def maxScore(self, nums1: List[int], nums2: List[int], k: int) -> int:
        pairs = [(a, b) for a, b in zip(nums1, nums2)]
        pairs.sort(key=lambda x: -x[1])

        tkh = [x[0] for x in pairs[:k]]
        tks = sum(tkh)
        heapq.heapify(tkh)

        answer = tks * pairs[k-1][1]

        for i in range(k, len(nums1)):
            tks -= heapq.heappop(tkh)
            tks += pairs[i][0]
            heapq.heappush(tkh, pairs[i][0])

            answer = max(answer, tks * pairs[i][1])
        
        return answer