참고
문제해설
NOTE
•
입력 값 ⇒ 비내림차순 정수 배열 2개와, 정수 k
•
출력 값 ⇒ 두 정수배열의 쌍중 가장 합이 적은 k개의 리스트
문제 로직고민
NOTE
•
처음에 문제 풀이를 오해해서 굉장히 애먹었다. 이문제의 핵심은 heap보다는 순서쌍의 합을 어떻게 최소값으로 뽑아낼 수 있는지 로직을 고민하는것이었다.
◦
모든 순서쌍을 넣고 최소값을 뽑기에는, 2개의 배열크기가 클수록 비효율적이다.
◦
하지만 2개의 배열에서 순서쌍의 합을 효율적으로 고르는건 생각보다 까다로운일이었다.
•
어떻게 순서쌍의 최소합을 효율적으로 뽑는가?
◦
순서쌍이 조합이 아니라, 순열이라서 상당히 까다롭다.
◦
처음은 (0,0) 일지라도, 다음이 (1,0), (0,1)일지 모르며 그다음은 (0,2), (1,2) .. 많은 가능성이 존재한다.
◦
사실 여기서 2시간정도 코드를 구현해보면서 많은 방식을 시도해보았지만 메모리초과나, 시간초과가 발생했다.
◦
결국 코드에 대한 힌트를 보았는데, 그리디 알고리즘을 이용해서 해결한다.
•
해결 방법 로직
1.
nums1의 각 원소와 num2의 1번째 원소와의 쌍을 힙에 추가한다. (해당 순서쌍은 작을 가능성이 가장 높다.)
•
nums1 = [1,7,11], nums2 = [2,4,6] ⇒ (1,2), (7,2), (11,2) 추가
2.
힙에서 가장 작은 쌍을 추출한다. 그런다음 추출한 쌍의 num2의 다음원소와 num1의 현재 원소를 추가한다.
•
[1,2] 추출, [1,4] 추가
•
[1,4] 추출, [1,6] 추가
•
[1,6] 추출, 6은 nums2의 마지막이므로 추가는 생략한다.
•
[7,2] 추출, [7,4] 추가
•
[7,4] 추출, [7,6] 추가
•
[11,2] 추출, [11,4] 추가
작성코드
NOTE
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
MinHeap heap = new MinHeap(k);
List<List<Integer>> result = new ArrayList<>();
if (nums1.length == 0 || nums2.length == 0 || k == 0) {
return result;
}
// 초기에 nums1의 각 원소에 대해 nums2의 첫 번째 원소와의 쌍을 힙에 추가
for (int i = 0; i < nums1.length && i < k; i++) {
heap.insert(new int[] { i, 0, nums1[i] + nums2[0] });
}
while(k-- > 0 && !heap.isEmpty()) {
int[] current = heap.pop();
result.add(Arrays.asList(nums1[current[0]], nums2[current[1]]));
if (current[1] == nums2.length - 1) continue;
heap.insert(new int[]{current[0], current[1] + 1, nums1[current[0]] + nums2[current[1] + 1]});
}
return result;
}
}
class MinHeap{
int[][] array;
int n;
MinHeap(int k){
array = new int[k][3];
n = 0;
}
public boolean isEmpty(){
return n==0;
}
public int[] pop(){
int[] result = array[0];
array[0] = array[--n];
bubbleDown(0);
return result;
}
public void insert(int[] v){
array[n++] = v;
bubbleUp(n-1);
}
private void bubbleDown(int i){
int left = i*2 + 1;
int right = i*2 + 2;
int root = i;
if(left < n && array[root][2] > array[left][2]) root = left;
if(right < n && array[root][2] > array[right][2]) root = right;
if(root != i){
swap(root, i);
bubbleDown(root);
}
}
private void bubbleUp(int i){
if(i <= 0) return;
int parent = (i-1)/2;
if(parent >= 0 && array[parent][2] > array[i][2]) {
swap(parent, i);
bubbleUp(parent);
}
}
private void swap(int a, int b){
int[] temp = array[a];
array[a] = array[b];
array[b] = temp;
}
}
Java
복사
100% 푼 문제가 아니라서 결과는 생략한다.