[python3] 23. Merge k Sorted Lists

풀이 일자: 23.03.12

난이도: [Hard]

분류: [Linked List/ Divide and Conquer/ Heap / Merge Sort]

문제 내용

k개의 Linked-List가 담긴 array가 주어지면 모든 linkedlist를 숫자가 증가하는 순서대로 합치는 문제이다.

 

 

문제 해결 흐름

1. 가장 Naive한 방법은 lists에 있는 것을 다 읽어서 순서대로 붙여나가는 방법일 것이다.

→ linkedlist를 하나씩 읽어서 list에 넣고 이를 정렬하여 Linked-list를 만드는 방법이 있을 것이다.

→ 이 방법은 문제가 Hard 난이도이기 때문에 TLE가 나올 것임을 예상하고 사용하지 않았으나 공식 풀이에 포함되어 있는 것으로 보아 문제는 없을 것 같다.

 

 

 

2. 위의  방법에서 조금 바꿔 Sort하는 과정 대신 linkedList의 삽입 알고리즘을 사용하였다.

→ 첫 LinkedList를 기본으로 두고 다음 linkedlist에 있는 Node를 크기에 맞게 삽입하는 방법이다.

 

# 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:   # list에 아무것도 없는 경우
            return None;
        
        j = 0
        head = None;

        while(j < len(lists)):      #시작을 1개 이상의 원소를 포함하는 linkedlist로 시작
            if lists[j] != None:    # 이를 위해 찾는 과정
                head = lists[j];
                break;
            j += 1;

        for k in range(j + 1, len(lists)):   # linkedList의 시작점 이후부터 탐색
            i = lists[k]
            if i != None:                    # linkedList에 원소가 있을 경우
                curr = head
                prev = None;

                while(i and curr):           # 순서에 맞게 linkedlist 삽입 알고리즘 사용
                    if prev == None and i.val < curr.val:
                        tmp, i = i, i.next;
                        tmp.next = head;
                        head = tmp;
                        prev = tmp;
                        continue;

                    if i.val == curr.val: 
                        tmp = curr.next;
                        curr.next, i = i, i.next;
                        prev, curr = curr, curr.next;
                        curr.next = tmp
                    elif i.val > curr.val:
                        prev = curr
                        curr = curr.next
                    else:
                        prev.next, i = i, i.next;
                        prev = prev.next
                        prev.next = curr

                if i != None:                 # 다 순회하고 현재 탐색하는 linkedlist의 원소가 남았을 경우 그대로 뒤에 붙임
                    prev.next = i;

        return head;

=> LinkedList의 삽입 알고리즘을 사용한 방법으로 삽입시간이 줄겠지만 어차피 탐색을 해야하기에 시간은 많이 걸릴 것이라고 예상할 수 있다.

 

Time Complexity: O(N^2*K)

LinkedList의 개수(K)만큼 탐색이 돌아가며 답을 채워가는 LinkedList 내의 원소(N)와 비교대상인 LinkedList내의 원소(N)의 비교로 인하여 비교적 많은 시간이 들 것임을 예상할 수 있다.

 

Space Complexity: O(1)

새로 ListNode를 생성해가며 답을 만드는 것이 아니라 기존에 있는 Node를 자르고 붙여가며 답을 완성했기 때문에 공간복잡도는 1이라고 볼 수 있다.

 

 

 

3.자료구조를 사용해본다면?

→ 작은 것부터 순서대로 큰 순으로 ListNode를 붙여나가야 되니까 LinkedList의 val를 가지고 heap에 넣었다가 빼면 빠르겠다.

 

# 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 None;
        
        heap = list();
        head = None;

        for i in lists:      # heap에 넣었다가
            while(i):
                heapq.heappush(heap, i.val);
                i = i.next;
        
        while(len(heap)!=0):       # pop하면 작은 순으로 알아서 빠지기 때문에 그대로 ListNode를 붙여나감
            val = heapq.heappop(heap);
            if head == None:
                curr = head = ListNode(val);
            else:
                curr.next = ListNode(val);
                curr = curr.next;
                
        return head;

=> 자료구조인 Min-heap을 사용한 코드로 넣고 빼는 실행시간이 짧은 것에 장점이 있다.

Time Complexity: O(N)

우선 모든 원소를 탐색해야하기 때문에 N, Heap의 insert Time Complexity는 LogN, pop Time Complexity는 1로 결과적으로 시간복잡도는 N이 될 것이다.( 70% ~ 95% 사이의 runtime이 나옴)

 

Space Complexity: O(N)

heap에는 모든 원소를 담아야 하기 때문에 N, TreeNode를 새로 생성해서 head에 붙여나가기 때문에 N, 결과적으로 공간복잡도는 N이 될 것이다.

 

 

 

다른 해결 방식

1. Divide and Conquer을 사용하는 Official Solution

=> 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]:
        amount = len(lists)
        interval = 1
        while interval < amount:
            for i in range(0, amount - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i + interval])
            interval *= 2

        return lists[0] if amount > 0 else None

    def merge2Lists(self, l1, l2):               # 2개씩 합친다.
        head = point = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l1
                l1 = point.next.next
            point = point.next

        if not l1:
            point.next=l2
        else:
            point.next=l1

        return head.next

=> 이 문제의 Solution 중 가장 좋은 알고리즘인 것 같다.

 

Time Complexity: O(NLogK)

2개씩 합쳐가기 때문에 LogK의 시간복잡도와 모든 노드를 순회해야하기 때문에 N의 시간이 걸리기 때문에 NLogK의 시간복잡도를 가지게 될 것이다.

 

Space Complexity: O(1)

공간복잡도는 새로 ListNode를 노드 수만큼 만들어낸 것이 아니기 때문에 1의 공간복잡도를 가지게 될 것이다.

 

문제 링크

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

Merge k Sorted Lists - LeetCode