[LeetCode] 23. Merge k Sorted Lists [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Merge k Sorted Lists - LeetCode>

1. 문제 (k개 정렬 리스트 병합)

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

2. 풀이

우선순위 큐를 이용한 풀이

• heapq 이용
• heapq.heappush(heap, (node.val, node))를 할 경우 node.val가 같을 경우 TypeError: '<' not supported between instances of 'ListNode' and 'ListNode' 라는 중복 오류가 발생하기 때문에 heapq.heappush(heap, (node.val, idx, node)) 와 같이 중간에 idx를 넣어 중복을 방지한다.

3. 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        root = ret = ListNode(None)
        heap = []

        # 각 연결 리스트의 루트를 힙에 저장
        for idx, node in enumerate(lists):
            if node:
              #    heapq.heappush(heap, (node.val, node)) # 중복 오류 발생
                heapq.heappush(heap, (node.val, idx, node))

        while heap:
            val, i, node = heapq.heappop(heap)
            ret.next, node = node, node.next
            ret = ret.next

            if node:
                heapq.heappush(heap, (node.val, i, node))

        return root.next

• 결과 :

방식	Status	Runtime	Memory	Language
우선순위 큐	[Accepted]	88 ms	18 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋