리트코드 - 2542. Maximum Subsequence Score

리트코드 - 2542. Maximum Subsequence Score

자연수 array nums1과 nums2 그리고 자연수 k가 주어질 때, {i_1, i_2, ..., i_k} 이렇게 k개의 index를 골라 다음을 계산한 것을 Subsequence Score라고 합니다.

(nums1[i_1] + ... + num1[i_k]) * min(nums2[i_1], ..., nums2[i_k])

이 때 Subsequence Score의 최댓값을 구하는 문제입니다. 오래 고민해봤지만 해결하지 못하고 solution을 찾았는데요, min(nums2[i_1], ..., nums2[i_k]) 자리에 올 수 있는 숫자가 n - k + 1 종류밖에 없다는 것에 초점을 두고 풀어나갑니다. 편의상 저걸 mini라고 하겠습니다.

먼저 nums1과 nums2를 index별로 짝을 지어두고, num2 기준으로 내림차순 정렬합니다. nums2를 읽으며 priority queue에 그 짝을 넣을겁니다. 그리고 priority queue 크기가 k를 넘으면 최솟값을 꺼내서 그 크기를 유지합니다.

이게 뭐하는거냐면, 정렬된 nums2 index 기준

mini가 nums2[x]일 때마다 왼쪽 (nums1[i_1] + ... + num1[i_k])의 최댓값을 구하는겁니다.

저 원소들을 구성하는 num1[i_j]가 각각 뭔지는 관심 없고 priority queue에 들어있는 것들 중 최솟값을 빼서 매번 Subsequence Score를 최대로 갱신하면 됩니다. 작은 예시를 가지고 직접 써보시면 이해하는 데 도움이 됩니다.

 

여담으로

Arrays.sort(pairs, (a, b) -> b[1] - a[1]);

에서 두번째 인자는 Comparator 자리인데, 저는 이게 종종 헷갈려서 이렇게 기억합니다.

1. Arrays.sort(myArray); 는 오름차순 정렬이다.
2. 1번은 Arrays.sort(myArray, (a, b) -> a - b); 이거랑 같다.

 

import java.util.*;

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int[][] pairs = new int[nums1.length][2];
        long ans = 0;
        long sum = 0;

        for (int i = 0; i < nums1.length; i++) {
            pairs[i] = new int[] {nums1[i], nums2[i]};
        }

        Arrays.sort(pairs, (a, b) -> b[1] - a[1]);

        for (int[] pair : pairs) {
            pq.add(pair[0]);

            sum = (sum + pair[0]);
            
            if (pq.size() > k) {
                sum -= pq.poll();
            }

            if (pq.size() == k) {
                ans = Math.max(ans, (sum * pair[1]));
            }
        }

        return ans;
    }
}