문제

https://leetcode.com/problems/find-k-pairs-with-smallest-sums/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• nums1에서 추출한 값을 x, nums2에서 추출한 값을 y라고 가정
• PriorityQueue를 활용하여 x + y 값이 작은 값을 우선순위가 높게하여 해결하려 함 => nums1, nums2의 최대 길이가 100,000개이기 때문에 시간 초과 + 메모리 초과가 발생
• 이를 해결하기 위해 아래의 조건들을 추가함

1. nums1, nums2는 정렬된 상태로 들어오기 때문에 모든 값을 조회할 필요 없이 각각 최대 k개만 조회하면 됨
2. PriorityQueue를 오름차순이 아닌 내림차순으로 수정하고, PriorityQueue의 크기가 k인 경우 pq.peek().x + pq.peek().y와 nums1[i] + nums2[j]를 비교했을 때, nums1[i] + nums2[j]가 크다면 PriorityQueue에 추가하지 않고, 더 이상 j를 증가시킬 필요가 없음

• 위 2가지 조건을 추가하여 시간초과, 메모리초과 문제를 해결함

코드

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<Pair> pq = new PriorityQueue<>();

        for (int i = 0 ; i < Math.min(nums1.length, k) ; i ++) {
            for (int j = 0 ; j < Math.min(nums2.length, k) ; j ++) {
                if (pq.size() == k) {
                    Pair temp = pq.peek();

                    if (temp.x + temp.y <= nums1[i] + nums2[j]) {
                        break;
                    } else {
                        pq.poll();
                        pq.add(new Pair(nums1[i], nums2[j]));
                    }
                } else {
                    pq.add(new Pair(nums1[i], nums2[j]));
                }
            }
        }

        List<List<Integer>> answer = new ArrayList<>();
        while(k > 0 && !pq.isEmpty()) {
            Pair pair = pq.poll();
            List<Integer> temp = new ArrayList<>();
            temp.add(pair.x);
            temp.add(pair.y);

            answer.add(temp);
            k --;
        }
        Collections.reverse(answer);
        return answer;
    }
}

class Pair implements Comparable<Pair> {
    int x, y;
    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compareTo(Pair pair) {
        // x + y를 기준으로 내림차순 정렬
        return pair.x + pair.y - this.x - this.y;
    }
}

결과