23. Merge k Sorted Lists

k 개의 Sorted Linked List 를 합친 Sorted Linked List를 만드는 문제이다.

 

2개 있었던 저번문제와 같이 접근하여, k개를 비교하여 작은 수부터 차례로 넣는 방법을 사용했다.

 

하지만, 맨 마지막 Test 예제를 시간초과로 통과하지 못했다.

[1][2][3][4][5][6]....과 같이 1개만 들어있는 리스트가 무수히 많은 예였다.

이 경우, 내 방식대로 한다면 O(n^2) 이기 때문에 시간초과한 것 같았다.

 

다른 사람들의 솔루션들을 보면

1. 우선순위 큐
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[ListNode]) -> ListNode:  
        result = ListNode()
        head = result
        while True:
            mi = 10001
            flag = 1
            for i in range(len(lists)):
                if lists[i] == None:
                    pass
                elif mi > lists[i].val:
                    mi = lists[i].val
                    temp = i
                    flag = 0
            if flag == 1:
                break
            
            result.next = ListNode()
            result = result.next
            result.val = mi
            lists[temp] = lists[temp].next
            
        return head.next

 

 

* 분할정복 방법

 

분할정복 소스코드

# 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:
        interval = 1
        while interval < len(lists): # 전체 길이보다 interval이 커질 때 동작 그만
            for i in range(0,len(lists)-interval,interval*2): # divide and conquer이기 때문에 interval*2의 step
                lists[i] = self.merge2lists(lists[i], lists[i+interval]) # self를 붙여야 한다.(클래스 내 자신의 함수 호출이기 때문에)
            interval *= 2 # interval을 2배 해주어 다음 병합 수행
        if len(lists) == 0: # 비어있는 lists 처리
            return
        else:
            return lists[0]
        
    def merge2lists(self, l1, l2): #두 ListNode 합치는 함수
        head = temp = ListNode()
        while l1 or l2:
            temp.next = ListNode()
            temp = temp.next
            if not l1:
                temp.val = l2.val
                l2 = l2.next
            elif not l2:
                temp.val = l1.val
                l1 = l1.next
            elif l1.val < l2.val:
                temp.val = l1.val
                l1 = l1.next
            else:
                temp.val = l2.val
                l2 = l2.next
        return head.next