[LeetCode/Hard] 23. Merge k Sorted Lists (JAVA)

문제

---

풀이

1차 풀이: 하나씩 합치기

가장 먼저 떠올린 풀이는, 두 ListNode를 merge sort 하듯이 합치는 것을 k-1번 반복하는 것이었다. 두 개의 ListNode를 합친 것을 answer에 저장하고, 또 이 answer와 다음 ListNode를 합쳐 answer를 업데이트 해나가는 것이다.

이 풀이의 시간복잡도는 O(nk)이다. n번의 탐색을 k-1번 반복하기 때문이다. 또한, 공간복잡도는 O(1)이다. 추가로 필요한 공간이 없기 때문이다.

class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        ListNode answer = null;
        
        int idx = 0;
        while (idx < k)
            answer = merge(answer, lists[idx++]);
        
        return answer;
    }
    
    private ListNode merge(ListNode left, ListNode right) {
    
        if (left == null) return right;
        if (right == null) return left;
        
        ListNode merged = null;
        if (left.val <= right.val) {
            merged = left;
            left = left.next;
        } else {
            merged = right;
            right = right.next;
        }
        
        ListNode current = merged;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                current.next = left;
                left = left.next;
            } else {
                current.next = right;
                right = right.next;
            }
            current = current.next;
        }
        
        if (left != null) current.next = left;
        if (right != null) current.next = right;
        
        return merged;
    }
}

하지만 LeetCode에 위 코드를 제출한 결과...

런타임 효율이 쓰레기였다! 그래서 더 좋은 방식은 무엇이 있을지 고민했다.

2차 풀이: 둘 씩 합치기

k개의 ListNode를 둘 씩 짝지어서 합치면, merge 횟수가 log(k)로 줄어든다. 예시로 8개의 ListNode를 합치려면 2개씩 짝지어 합쳐서 4개의 ListNode 만들고, 또 4개를 2개로 만들고, 2개를 1개로 합치는 식으로 병합을 하는 것이다. 이렇게 하면 시간복잡도가 O(nlog(k))로 크게 감소한다.

코드는 mergeKLists()만 약간 변동이 있고 merge()는 1차 풀이와 동일하다.

class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;     
        
        int interval = 1;
        while (interval < k) {
            int idx = 0;
            while (idx + interval < k) {
                lists[idx] = merge(lists[idx], lists[idx+interval]);
                idx += interval * 2;
            }
            interval *= 2;
        }
        return k == 0 ? null : lists[0];
    }
    
    private ListNode merge(ListNode left, ListNode right) {
    
        if (left == null) return right;
        if (right == null) return left;
        
        ListNode merged = null;
        if (left.val <= right.val) {
            merged = left;
            left = left.next;
        } else {
            merged = right;
            right = right.next;
        }
        
        ListNode current = merged;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                current.next = left;
                left = left.next;
            } else {
                current.next = right;
                right = right.next;
            }
            current = current.next;
        }
        
        if (left != null) current.next = left;
        if (right != null) current.next = right;
        
        return merged;
    }
}

런타임이 확연히 줄어든 것을 확인할 수 있었다!

---

참고

Merge K Sorted Lists