LeetCode 23. Merge k Sorted Lists

개발공부를해보자·2025년 1월 18일

LeetCode

목록 보기

27/95

파이썬 알고리즘 인터뷰 문제 27번(리트코드 23번) Merge k Sorted Lists
https://leetcode.com/problems/merge-k-sorted-lists/

나의 풀이1

# 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[Optional[ListNode]]) -> Optional[ListNode]:
    
        if len(lists) == 0:
            return

        result = ListNode(0)
        curr = result

        while True:
            min_head = ListNode(float("inf"))
            min_index = -1
            for i, head in enumerate(lists):
                if head and head.val < min_head.val:
                    min_head = head
                    min_index = i

            if min_index >= 0:
                curr.next = min_head
                curr = curr.next
                #min_head = min_head.next #이건 안되고
                lists[min_index] = lists[min_index].next #이건 되네?
            else:
                break
        return result.nex

나의 풀이2

# 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[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return

        root = ListNode()
        curr = root

        while None in lists:
            lists.remove(None)
        
        while lists:
            lists = sorted(lists, key = lambda node: node.val, reverse = True)
            node = lists[-1]
            curr.next = node
            curr = curr.next
            node = node.next
            if node:
                lists[-1] = node
            else:
                lists.pop()

        return root.next

다른 풀이1(책 풀이, 힙 Heap, 우선순위 큐 Priority queue)

# 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[Optional[ListNode]]) -> Optional[ListNode]:
        root = result = ListNode(None)
        heap = []

        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i, lists[i])) 
                #(lists[i].val, lists[i]) 는 오류. val이 같은 경우 ListNode끼리 대소 비교 불가
        
        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

다른 풀이2(리트코드 Solution, 분할 정복 Divide and Conquer)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if not l1:
            return l2
        if not l2:
            return l1

        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        return self.divideAndConquer(lists, 0, len(lists) - 1)

    def divideAndConquer(self, lists: List[Optional[ListNode]], left: int, right: int) -> Optional[ListNode]:
        if left == right:
            return lists[left]

        mid = left + (right - left) // 2
        l1 = self.divideAndConquer(lists, left, mid)
        l2 = self.divideAndConquer(lists, mid + 1, right)
        return self.mergeTwoLists(l1, l2)

오답1

파이썬 연결 리스트를 다룰 때 흔히 실수하는 참조 업데이트 문제
min_head = lists[0], min_head = min_head.next
라고 하더라도 lists[0]은 바뀌지 않는다. min_head는 복사본이라 생각하면 된다. 복사본만 바뀌는 것이다.
이에 대한 자세한 내용

오답2

(정답) heapq.heappush(heap, (lists[i].val, i, lists[i]))
(오답) heapq.heappush(heap, (lists[i].val, lists[i]))
여기서 lists[i]는 연결리스트의 node이다.
오답이 틀린 이유는, 파이썬에서 tuple의 대소 비교는 앞에서부터 사전식으로 이루어진다.
그런데 같은 값을 가지는 node가 있는 경우 첫 번째 성분이 같으므로 두 번째를 비교해야하는데, 두 번째는 node이다.
그런데 node는 대소비교가 불가능하므로 오류가 발생한다.

배운 점

우선, 정렬된 두 Linked List를 병합하는 문제를 이전에 풀었다. k개로 늘어났다면 당연히 위 문제 풀이를 이용할 생각을 했어야 했는데 그러지 못했다. 분할 정복을 떠올리지 못한 것이 아쉽다.
다음으로 heap 자료 구조에 대해서는 알고 있었지만 실제로 이를 이용한 문제를 풀어본 적이 없어서 떠올리지 못했다.
heap이란 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 완전 이진 트리이며, 부모의 값은 자식의 값보다 항상 크거나(max heap) 작다(min heap). 완전 이진 트리이므로 데이터의 삭제/삽입 모두 O(log(N))이다.
heap에 대한 자세한 글