Merge k Sorted Lists

Merge k Sorted Lists

문제

주어진 N개의 Linked List가 주어지고, 이 N개의 Linked List를 Merge후 오름차순 정렬한 하나의 Linked List를 반환하라

 

접근방법

가장 쉬운 방법은 N개의 Node중 첫번째 노드의 Value를 상호 비교 하면서 List를 하나씩 Pop 하는 방법이다.

이방법을 사용하면 List의 갯수 만큼 Compare가 필요하다.

상기 그림을 보면 

1,3,7 => 3번을 Compare하고

2,3,7 => 3번을 Compare하고

....

7 => 1번을 Compare하게 되는데 

만약에 3개의 Linked List가 동일한 Node의 갯수를 갖게 된다면 최악의 경우

O(numberOfList * Node) 만큼의 시간 복잡도를 갖게 된다.

그래서 다른 방법으로는

Priority Queue로 접근 하는 것이 가장 쉽다.

일단 N개의 모든 Node에 각 value 값을 Weight로해서 Priority Queue에 넣게 되면

가장 낮은 값부터 Poll 시키면 된다.

상기와 같이 Priority Queue는 순서를 유지하진 않지만 Max나 Min 또는 주어진 Comparator에 따라서 선택된 최상의 값을 Root에 Elements를 유지 할 수 있다.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> numbers = new PriorityQueue<>((x, y) -> x - y);


        for (int i = 0; i < lists.length; i++) {
            ListNode node = lists[i];

            while(node != null){
                numbers.offer(node.val);
                node = node.next;
            }
        }


        ListNode head = new ListNode(-1);
        ListNode node = head;

        while (0 < numbers.size()) {
            node.next = new ListNode(numbers.poll());
            node = node.next;
        }

        
        return head.next;

    }
}

이방법은 모든 Node를 넣을때 필요한 Node의 길이와

Queue에 입력할때 필요한 Log N

그리고 Pop할때 최대 필요한 1의 시간이 필요하다.

O(NLogN)

->

Leetcode 솔루션에서는 O(N log NumberOfLists)라고 답을 하고 있긴 하지만 아무리 생각해봐다 모든 Node를 Queue에 삽입하고 Pop을 하기 때문에 Log Offer의 횟수 + Log Poll의 횟수라고 보면 Log N이 맞지 않나 싶다.

내가 뭘 잘못 이해하고있나?