23 . Merge K sorted List(Linked List 정렬, Merge sort, 분할 정복)

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

Merge k Sorted Lists - LeetCode

 

---

난이도 hard 의 list 형태로 제시된 여러 linked list 를 정렬해서 합치는 문제입니다.

 

여러 풀이를 가지고 풀이를 짜봤는데요. l

먼저 linked list가 하나인 경우에는 곧 바로 그 linked list가 반환되도록 하고 , 비어있는 경우에는 return으로 직행하도록 했습니다. 이 다음에는 linked list가 하나가 아니기 때문에 순차적인 접근을 위해 2개의 리스트를 합치는 mergeTwoLists라는 기능을 따로 구현했습니다.

 

# 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) == 1:
            return lists.pop()
        if not lists:
            return
    
        def mergeTwoLists(list1,list2):
            if not list1:
                return list2
            if not list2:
                return list1
            
            if list1.val < list2.val:
                next_val = list1.next
                list1.next = mergeTwoLists(next_val,list2)
                return list1
            else:
                next_val = list2.next
                list2.next = mergeTwoLists(list1,next_val)
                return list2
        
        #방법 1
        mid = len(lists)//2
        l,r = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:])
        return mergeTwoLists(l,r)
       
       
       #방법 2
        # merged = lists[0]
        # for i in range(1,len(lists)):
        #     merged = mergeTwoLists(merged,lists[i])
        # return merged

 

사실 방법 2를 먼저 시도했었는데 시간초과가 뜨더라구요. 방법2는 처음부터 끝까지 값을 비교하면서 매번 재정렬을 하기 때문에 시간이 많이 걸렸기 때문인데요

 

반면 방법1같은 경우에는 절반으로 나눠서 각각 정렬하고 합쳐주는 mergesort의 형태로 계산량을 확연히 줄여줌으로써 통과가 될 수 있었습니다.

 

 

728x90

---

다른 풀이에서 구성은 같지만 훨씬 간결한 표현들을 볼 수 있었는데요

 

class Solution(object):
    def mergeKLists(self, lists):
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        mid = len(lists) // 2
        l, r = self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:])
        return self.merge(l, r)
    
    
    #방법 1 (dummynode를 사용하는 방법)
    def merge(self, l, r):
        dummy = p = ListNode()
        while l and r:
            if l.val < r.val:
                p.next = l
                l = l.next
            else:
                p.next = r
                r = r.next
            p = p.next
        p.next = l or r
        return dummy.next
    
    #방법 2 (dummynode없이 합치는 방법)
    def merge1(self, l, r):
        if not l or not r:
            return l or r
        if l.val< r.val:
            l.next = self.merge(l.next, r)
            return l
        r.next = self.merge(l, r.next)
        return r

 

OldCodingFarmer님의 코드로 두 개의 linked list를 합치는 대표적인 2가지 방법을 효과적으로 간결하게 제시한 모습이 

인상적인 것 같습니다. 

 

 

반면에 heap 을 이용한 경우도 있었는데요

 

Heapq 이용 풀이)

heap = [(head.val, i, head) for i,head in enumerate(lists) if head]
        heapify(heap)
        dummy = ListNode(0)
        curr = dummy
        while heap != []:
            val, i, node = heap[0]
            if not node.next: # exhausted one linked-list
                heappop(heap)
            else:
                heapreplace(heap, (node.next.val, i, node.next)) 
            curr.next = node    
            curr = curr.next
        return dummy.next

 

heap에 각 개별 linked list의 head값, 인덱스값 head를 담은 리스트를 만들고, heap에서 가장 작은 값을 pop하고 새로운 아이템을 push 하는 heapreplace를 활용해서 새로운 값을 넣어도 가장 작은 값으로 curr 이 이동되도록 했습니다.