자연수 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
자리인데, 저는 이게 종종 헷갈려서 이렇게 기억합니다.
Arrays.sort(myArray);
는 오름차순 정렬이다.- 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;
}
}