[Heap / Priority Queue, Medium] Maximum Subsequence Score

https://leetcode.com/problems/maximum-subsequence-score/description/?envType=study-plan-v2&envId=leetcode-75

처음에 감이 안와서 힌트봄
힌트에 nums2를 기준으로 정렬하면 좋겠다고 써있다.

그럼 nums1과 nums2 인덱스를 쌍으로 엮은 pair를 만들어 num2 값 기준으로 정렬한다.

페어 배열을 순회하면서 우선순위 큐를 이용해 누계를 갱신한다.
페어 배열은 이미 nums2 값 기준으로 내림차순 정렬되었으므로 min값 최대부터 탐색함을 보장한다.

이제 배열을 순회하면서 우선순위 큐에 nums1 값을 누적하고,
큐 사이즈가 k보다 커지면 빼주고
큐 사이즈가 k와 같아질 때는 sum * p[1] 로 최대값을 갱신해준다. (p1은 nums2의 값)

1번 예시 기준
nums1 = [1,3,3,2], nums2 = [2,1,3,4], k = 3이면
[[2, 4], [3, 3], [1, 2], [3, 1]] 이렇게 정렬된 상태

큐사이즈 == k 라는 것은 nums2의 가장 작은 값과 매칭된다는 것
즉, 3번째 순회에 (2+3+1) * 2가 되고 그 다음에는 (2+3+3) * 1

직관적으로 요약하자면

• 우선순위 큐는 nums1에 대한 오름차
• pairs 순회는 nums2에 대한 내림차
• 둘이 만나는 순간마다 max 갱신

class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        int n = nums1.length;

        int[][] pairs = new int[n][2];
        for (int i=0; i<n; i++) {
            pairs[i] = new int[] {nums1[i], nums2[i]};
        }
        Arrays.sort(pairs, (p1, p2) -> p2[1] - p1[1]);

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        long max = 0;
        long sum = 0;

        for (int[] p : pairs) {
            pq.offer(p[0]);
            sum += p[0];

            if (pq.size() > k) {
                sum -= pq.poll();
            }
            if (pq.size() == k) {
                max = Math.max(max, sum * p[1]);
            }
        }
        return max;
    }
}