[LeetCode,Python] 23. k개 정렬 리스트 병합(Merge k Sorted Lists)

k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.

 

Input: lists = [[1,4,5], [1,3,4], [2,6]]

Output: [1,1,2,3,4,4,5,6]

 

Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ]

 

merging them into one sorted list: 1->1->2->3->4->4->5->6

 

 

** 깔끔한 답안 **

 

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        root = result = ListNode(None)
        heap = []
 
        # 각 연결 리스트의 루트를 힙에 저장
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val,i,lists[i]))
                
        # 힙 추출 이후 다음 노드는 다시 저장
        while heap:
            node = heapq.heappop(heap)
            idx = node[1]
            result.next = node[2]
            
            result = result.next
            if result.next:
                heapq.heappush(heap, (result.next.val, idx, result.next))
                
        return root.next

 

해설:

 

우선순위 큐를 이용하면 쉽게 풀 수 있는 문제이다.

대부분의 우선순위 큐 풀이에 거의 항상 heapq 모듈이 쓰이는데

왜 Priorityqueue를 놔두고 heapq를 쓸까?

 

PriorityQueue 내부를 들여다보면 답을 알 수 있다.

_put과 _get에는 그대로 headpush와 headpop이 쓰여 겉 보기엔 둘은 동일해 보인다.

하지만 PriorityQueue는 스레드 세이프(Thread-Safe)를 보장하고 heapq는 보장하지 않는다.

 

스레드 세이프란,

멀티 스레드에도 안전한 프로그래밍 개념으로 멀티 스레딩을 지원한다고 생각하면 된다.

 

하지만 파이썬 GIL 특성상 멀티 스레딩이 거의 의미가 없고

스레드 세이프를 보장한다는 얘기는 내부적으로 락킹(Locking)을 제공한다는 의미이므로

락킹 오버헤드가 발생해 성능에 영향을 끼친다.

 

따라서 굳이 멀티 스레드로 구현할 게 아니라면 heapq 모듈을 쓰는 것이 속도 면에서 바람직하다.

 

코드로 돌아와서

 

line 14를 보면 heap 안에 lists [i]. val, i, lists [i]이 입력된다고 보면 된다.

하지만 굳이 i를 넣는 이유는

입력 예시에서 [1 4 5], [1 3 4]가 있는데

lists [i]. val을 해버리면 둘 다 1이어서 중복된 값을 넣게 되는 것으로 받아들여 TypeError가 발생하게 된다.

 

따라서 i를 추가하여 구별해주면 이 문제가 해결된다.

그래서 i는 이 용도 이외에는 사용할 일이 없다.

 

그 후 heap에서 heappop을 통해 노드를 꺼내 주는데

1->4->5를 통째로 꺼내서 1을 취하고 4->5는 다시 넣어

가장 작은 노드가 항상 차례대로 나올 수 있도록 한다.