[LeetCode] 2542. Maximum Subsequence Score

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

Maximum Subsequence Score - LeetCode

문제 유형 : 우선순위 큐

문제 난이도 : Medium

 

문제

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.

 

nums1에서 k개를 고르고, nums2에서 같은 인덱스들 중 가장 작은 수를 곱하였을 때, 가장 큰 수를 구해라.

 

풀이

nums1의 요소들과 같은 인덱스인 nums2 요소들끼리 묶어서 새로운 배열을 만든다.

그 뒤, 우선순위 큐에 순서대로 K개를 넣는다. (최소 힙으로만든다)

그 뒤, 가장 큰 수를 매번 갱신하며 나머지 요소들을 넣어보며, 넣을 때마다 기존 우선순위 큐에서 pop시킨다(가장 작은애를 탈락) 

 

코드(C++)

class Solution {
public:
    long long maxScore(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<pair<int, int>> v;
        for(int i = 0; i < nums1.size(); i++){
            v.push_back({nums2[i], nums1[i]});
        }

        sort(v.rbegin(), v.rend());

        long long ans = 0;

        long long curr_sum = 0;

        priority_queue<int, vector<int>, greater<int>> pq;

        for(int i = 0; i < k-1; i++){
            curr_sum += v[i].second;

            pq.push(v[i].second);
        }

        for(int i = k-1; i < nums1.size(); i++){
            curr_sum += v[i].second;

            pq.push(v[i].second);

            ans = max(ans, curr_sum * v[i].first);

            curr_sum -= pq.top();

            pq.pop();
        }

        return ans;
    }
};