[LeetCode#23] Merge K sorted Lists

❒ Description

---

제목	Merge K sorted Lists
링크	https://leetcode.com/problems/merge-k-sorted-lists/description/
자료구조	선형 (우선순위 큐)
시간복잡도	O(nlogk)

 

이번 문제에서도 가상의 노드 Root를 사용되었다. 이쯤 느껴지는 것은 뭔가 정렬이 들어가는

경우에는 가상의 노드 접근을 생각해보는 것도 좋은 거 같다.

 

아무튼 문제의 핵심은 자료구조 Priority Queue를 사용해서 해결하는 문제였다.

Priory Queue에 대한 정리는 이곳에 할 것이다. 

 

 

 

❒ Solution

---

전체 코드

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> {
        if (o1.val == o2.val) {
            return 0;
        } 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()) {
        ListNode poll = pq.poll();
        tail.next = poll;
        tail = tail.next;
        if (tail.next != null) {
            pq.add(poll.next);
        }
    }
    return root.next;
}

 

1. Priority Queue 인스턴스 생성 (with. Compator)

PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> {
    if (o1.val == o2.val) {
        return 0;
    } else if (o1.val > o2.val) {
        return 1;
    } else {
        return -1;
    }
});

• `o1.val == o2.val` : 동일한 값이면 무시
• `o1.val > o2.val` : 새로운 값(o1)이 기본 값(o2) 보다 크면 뒤에 위치
• `그 외` : 작으면 앞에 위치

여기서는 Priority Queue 요소들의 크기를 비교하는 Comparator를 작성해준다.

이렇게 해줘야 Q에 새로운 요소를 삽입할 때 작은 값이 맨 앞에 위치하게 된다.

 

 

2. while loop

 

while (!pq.isEmpty()) {
    ListNode poll = pq.poll();
    tail.next = poll;
    tail = tail.next;
    if (tail.next != null) {
        pq.add(poll.next);
    }
}

 

문제에서 주어진 input 값은 `[ [1, 4, 5], [1 , 3, 4] ,[2 ,6] ]` 이다.

• 1 → 4 → 5
• 1 → 3 → 4
• 2 → 6

pq	tail
[1, 1, 2]	1
[1, 2, 4]	1 -> 1
[2, 4, 3]	1 -> 1 -> 2
[3, 4, 6]	1 -> 1 -> 2 ->  3
[4, 6, 4]	1 -> 1 -> 2 -> 3 -> 4
[4, 6, 5]	1 -> 1 -> 2 -> 3 -> 4 -> 4
[5, 6]	1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5
[6]	1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6