[Leetcode Top Interview 150] 373. Find K Pairs with Smallest Sums

난이도 : medium

문제링크

• 2개의 integer 리스트 nums1, nums2와 숫자k가 주어진다
  • 리스트는 non-decreasing order이다
• 합이 작은 순서대로 k 개의 두 배열의 원소로 구성된 pair들을 리턴하세요

 

1. 접근법

• 합이 작으려면, 작은 숫자부터 뽑아서 pair를 구성해야 함
• 최소힙 자료구조를 사용하여 pair를 만든다

 

2. 의사코드

// 좌표의 합을 가지고 오름차순한 우선순위 큐를 생성한다
PriorityQueue<int[]> pq = new PriorityQueue<>(
        (a, b) -> (a[0] + a[1]) - (b[0] + b[1])
);

// pq에 원소들을 모두 넣고
for (int n1 : nums1) {
	for (int n2 : nums2) {
		pq.offer(new int[] {n1, n2});
	}	
}

// k가 0이 아닐때가지, pq가 원소를 가지고 있을때까지 반복
while (k-- < 0 && !pq.isEmpty()) {
	result.add(pq.peek()[0], pq.peek()[1]);    
}

return result;

 

3. 구현 코드

PriorityQueue<int[]> pq = new PriorityQueue<>(
        (a, b) -> (a[0] + a[1]) - (b[0] + b[1])
);


for (int n1 : nums1) {
	for (int n2 : nums2) {
		pq.offer(new int[] {n1, n2});
	}	
}

List<int[]> result = new ArrayList<>();
while (k-- < 0 && !pq.isEmpty()) {
	result.add(pq.peek()[0], pq.peek()[1]);    
}

return result.stream()
			 .map(arr-> Arrays.stream(arr).boxed().collect(Collectors.toList()))
             .collect(Collectors.toList());

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n*m) - 모든 노드를 순회함
• 공간복잡도 : O(n*m) - 모든 노드를 생성해야 함

 

5. 개선점

• 시간복잡도 때문에 통과하지 못했다

 

6. 회고

• 도저히 생각이 안나 풀이를 찾아보았다

    public List<List<Integer>> solutionKSmallestPairs(int[] nums1, int[] nums2, int k) {
        if (nums1.length == 0 || nums2.length == 0) {
            return new ArrayList<>();
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (a, b) -> (a[0] + a[1]) - (b[0] + b[1])
        );

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

        List<int[]> result = new ArrayList();
        while (k-- > 0 && !pq.isEmpty()) {
            int[] cur = pq.poll();
            int i = cur[2], j = cur[3];
            result.add(new int[] {cur[0], cur[1]});
            if (j+1 < nums2.length) {
                pq.offer(new int[] {nums1[i], nums2[j+1], i, j+1});
            }
        }

        return result.stream()
                .map(arr -> Arrays.stream(arr).boxed().collect(Collectors.toList()))
                .collect(Collectors.toList());
    }

(출처 : https://segmentfault.com/a/1190000008309330)

 

• 시간복잡도를 줄이기 위해 온갖 조건을 걸었다
• 모든 배열을 우선순위 큐에 넣는 것이 아닌, nums2를 한줄씩 넣으면서 k값이 0이 될때 빠져나오도록 하였음