nums1 리스트와 nums2 리스트의 순서쌍 중 순서쌍의 합이 가장 작은 k개의 순서쌍을 출력하는 문제
힌트 1. nums1의 길이는 10만, nums2의 길이도 10만이지만 k는 1만개밖에 되지 않는다. 최대 nums1[k-1] + nums2[0]이거나 nums1[0] + nums2[k-1] 까지만 찾아도 되기 때문에 최대 k제곱번만 돌아도 된다. 10만 -> 1만으로 확 줄일 수가 있다.
힌트 2. nums1[0]과 nums2[0]을 비교했다면 그 다음 비교해야 하는 수는 nums1[0]과 nums2[1]이다. nums1[0]과 nums2[2], nums1[0]과 nums2[3]을 벌써 체크할 필요는 없다.
힌트 3. nums1[0]부터 nums1[k-1]까지의 값들과 nums2[0]의 값들을 모두 min-heap에 넣는다. 그리고 최솟값을 뺀다. 그 다음으로 가장 가능성 있는 순서쌍은 이번에 뺀 순서쌍에서 nums2의 인덱스를 하나 증가한 값이다
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> resV = new ArrayList<>(); // Result list to store the pairs
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
// 1. nums1의 모든 값들과 nums2의 0번째 인덱스를 더한 값 모두 최소힙에 넣기
int idx = 0;
for(int num : nums1){
// 1-1 . 1번째는 nums1의 값, 2번째는 순서쌍의 합(최소힙 Comparator에 사용), 3번째는 num2의 인덱스
pq.add(new int[]{num, num + nums2[0], 0});
idx++;
if(idx == k) break;
}
List<List<Integer>> ans = new ArrayList<>();
// 2. Heap에서 하나를 뽑아서 정답 리스트에 추가하고 그 다음으로 가능성 있는 수를 Heap에 넣기
while(k-- > 0){
if(pq.isEmpty()){
return ans;
}
int[] cur = pq.poll();
List<Integer> lst = new ArrayList<>();
// 2-1. 최소값의 nums1, nums2값 넣기
lst.add(cur[0]);
lst.add(nums2[cur[2]]);
ans.add(lst);
// 2-2 . 가능성 있는 수 heap에 넣기
if(cur[2] + 1 < nums2.length){
pq.add(new int[]{cur[0], cur[0]+nums2[cur[2]+1], cur[2]+1});
}
}
return ans;
}
}
속도는 잘 나오지만 메모리가 간당간당 해져버린다.
메모리를 어떻게 줄여야 할지는 감이 잡히질 않는다...