373. Find K Pairs with Smallest Sums

---

문제 분석

정수 배열 2개가 주어진다.
2개의 배열의 값들을 더하여 나올 수 있는 경우의 수 중
가장 작은 값을 순서대로 k 번까지 리턴하는 문제

---

풀이 과정

2개의 정수 배열에서 값을 꺼낸 합을 PriorityQueue 에 담는다.
알아서 정렬이 될테고 k 번 만큼 poll() 하여 꺼내면 된다.

1. nums1.length vs k 의 값 중 작은 값을 기준으로 nums1 을 담는다.
   이 때 nums2 는 0 번 인덱스값만 추가할 것이다.
2. PriorityQueue 에서 값을 꺼낼 때 추가적으로 nums2 의 다음 인덱스 값을 추가해준다.

아래는 PriorityQueue 에 사용할 class 다.

class Pair {
	int firstNumber;  	 <-- 첫 번째 숫자
    int secondNumber;    <-- 두 번째 숫자
    int sum;             <-- 두 숫자의 합
    int index;           <-- nums2[]에서 사용할 인덱스
}

예제 1) nums1 = [1,7,11], nums2 = [2,4,6], k = 3

1. nums1 담기

k 가 3 이고 nums1.length 도 3이다.
지금은 두 값이 같지만, 둘 중 작은 값으로 for 문을 돌리면 ArrayIndexOutOfBoundsException 이 발생하지 않는다.

nums2[0] 을 고정으로 PriorityQueue 에 값을 추가한다.
index 도 0으로 추가한다.

for (int i = 0; i < Math.min(k, nums1.length); i++) {
	pq.offer(new Pair(nums1[i], nums2[0], 0));
}

PriorityQueue 에 [1, 2], [7, 2], [11, 2] 이 담길 것이다.

index 를 0 으로 추가하는 이유는 이중포문으로 추가하면 시간초과가 나기 때문이다.
다음 반복문으로 정답에 값을 추가할 텐데 이때 index 를 하나씩 올려 값을 추가할 것이다.

2. 정답을 추가하고 nums2 담기

k 만큼 반복문을 돌면된다.
PriorityQueue.poll() 을 통해 값을 꺼낸 후 정답에 .add() 한다.

첫 번째 반복문에서의 값은 항상 최소값일테고
이 후 조건문을 통해 nums2[0] 의 다음 index 인 nums2[1] 을 추가해준다.
index 또한 +1 한다.

PriorityQueue 내부적으로 정렬이 될테고 다음 PriorityQueue.poll() 은
최솟값을 반환할 것이다. 당연히 정렬 기준은 sum 필드를 기준으로 한다.

while (k-- > 0 && !pq.isEmpty()) {
	Pair pair = pq.poll();
	result.add(Arrays.asList(pair.firstNumber, pair.secondNumber));
		if (pair.index < nums2.length - 1) {
			int newIndex = pair.index + 1;
			pq.offer(new Pair(pair.firstNumber, nums2[newIndex], newIndex));
		}
	}

---

나의 생각

2개의 정수 배열을 PriorityQueue 에 담을 때
이중 포문을 사용하면 시간이 초과된다.
하나의 배열을 먼저 추가하고 나머지 배열의 값을 꺼낼 수 있도록 필드에 index 를 두는 개념을 배웠다.

---

코드

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> result = new ArrayList<>();
        
        PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>(){
            @Override
            public int compare(Pair p1, Pair p2) {
                return p1.sum - p2.sum;
            }
        });

        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            pq.offer(new Pair(nums1[i], nums2[0], 0));
        }

        while (k-- > 0 && !pq.isEmpty()) {
            Pair pair = pq.poll();
            result.add(Arrays.asList(pair.firstNumber, pair.secondNumber));

            if (pair.index < nums2.length - 1) {
                int newIndex = pair.index + 1;
                pq.offer(new Pair(pair.firstNumber, nums2[newIndex], newIndex));
            }
        }

        return result;
    }
}

class Pair {
    int firstNumber;
    int secondNumber;
    int index;
    int sum;

    public Pair(int firstNumber, int secondNumber, int index) {
        this.firstNumber = firstNumber;
        this.secondNumber = secondNumber;
        this.index = index;
        this.sum = firstNumber + secondNumber;
    }
}