[LeetCode 23] Merge K Sorted Lists - 우선순위 큐

https://leetcode.com/problems/merge-k-sorted-lists/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

우선순위 큐에 정수를 넣는 방식 

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (ListNode list : lists) {
            while (list != null) {
                pq.add(list.val);
                list = list.next;
            }
        }

        ListNode head = new ListNode(0);
        ListNode next = head;

        while (!pq.isEmpty()) {
            int i = pq.poll();
            next.next = new ListNode(i);
            next = next.next;
        }
        return head.next;

    }

 

---

우선순위 큐에 객체를 넣는 방식 (compare() 메서드로 순서 정의)

처음 풀이는 각 연결리스트의 첫번째노드부터 끝까지 다 큐에 집어넣는 방식으로 하였다. 하지만 각 연결리스트는 오름차순으로 이미 정렬된 상태이다. 예를들면 다음과 같이 입력값이 [[1,4,5] , [1,3,4] , [2,7]]이면 반복문으로 각 연결 리스트의 첫 번째 노드를 우선순위큐에 저장한다.

 

큐에는 각 연결리스트이 루트인 1,1,2 가 저장된다. 그렇다면 이중에서 가장 작은 값을 지닌 노드를 꺼내고 그다음 노드를 다시 큐에 넣어주는 식으로 반복한다. 이렇게 하면 다시 새로운 노드를 만들 필요도 없고 시간복잡도 상으로 우선순위 큐는 내부적으로 힙 자료구조를 사용하여 요소를 저장한다

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.val == o2.val) {
                return 0;
            }
            // 새로운 값(o1)이 기본 값(o2)보다 크면 뒤에 위치
            else if (o1.val > o2.val) {
                return 1;
            } else {
                return -1;
            }
        });

        ListNode root = new ListNode(0);
        ListNode tail = root;

        for (ListNode node : lists) {
            if (node != null) {
                pq.add(node);
            }
        }
        
        while (!pq.isEmpty()){
            tail.next = pq.poll();
            tail = tail.next;
            
            if(tail.next != null)
                pq.add(tail.next);
        }
        return root.next;

    }

 

 

하지만 막상 돌려보니 두 풀이 모두 같은 런타임과 메모리를 쓴다..

 

시간 복잡도를 계산해보자.

힙을 사용함으로써 각 연산(삽입,삭제)의 시간복잡도는 O(log n)이다.  

 

1. 우선순위 큐 삽입: 모든 연결리스트의 첫 번째 노드를 우선순위 큐에 삽입하는 과정은 각 연결 리스트의 개수를 'k'라 할때 최대 'k'번의 삽입 연산이 일어난다. 따라서  kO(logk)라 볼 수 있다.

 

2. 병합 과정: 각 노드를 우선순위 큐에서 꺼내 다음 노드를 삽입하는 과정은 모든 노드에 대해 한 번씩 수행된다. 전체 노드의 수를 'N'이라고 할때 이 과정의 시간복잡도는 'N'번의 우선순위 큐 연산을 포함하므로 NO(logk)가 된다.

 

총 시간 복잡도는 O(Nlogk + klogk) 이다..

 

첫번째 코드의 시간복잡도는 O(2NlogN) 이므로 상수항을 무시하면 결국엔 O(N logN)으로 표현할 수 있다.

 

둘 간의 큰 차이가 없는 게 당연한 것 이었다.