[LeetCode] 23. Merge k Sorted Lists

jw9603.log

LeetCode에서 처음으로 Hard 문제를 도전했습니다. 또한, 리트 코드에서 연결 리스트 유형의 마지막 문제입니다(제가 푸는,,,).

1. 오늘의 학습 키워드

Linked List
Priority Queue
Heap
Divide and Conquer

2. 문제: 23. Merge k Sorted Lists

단계: Hard
주제: Linked List, Divide and Conquer, Heap (Priority Queue), Merge Sort
출처: https://leetcode.com/problems/merge-k-sorted-lists/description/

Description

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= $10^4$
0 <= lists[i].length <= 500
$-10^4$ <= lists[i][j] <= $10^4$
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed $10^4$ .

3. 문제 풀이

Step1. 문제 이해하기

이 문제는 k개의 오름차순으로 정렬된 연결 리스트를 하나로 합치는 문제입니다. 마찬가지로 합치는 경우에도 오름차순은 유지해야 합니다.

입출력을 살펴보겠습니다.

Input:
- k는 0이상 $10^4$ 이하입니다. 즉, 리스트내에 연결 리스트들이 아예 없을수도 있습니다.
- 연결 리스트내 노드 개수는 0이상 500이하입니다.
- 모든 연결 리스트들의 노드의 총 개수는 $10^4$ 개를 넘지 않는다고 합니다.
Output:
- 병합된 연결 리스트를 반환합니다.

노드 개수가 최대 10^4개를 넘지 않는다고 합니다. 따라서 $O(n^2)$ 보다는 효율적인 코드로 구현해야 할 것 같습니다.

Step2. 문제 분석하기

입력으로 주어지는 lists내에 오름차순으로 정렬된 연결 리스트들이 있습니다.

이 연결 리스트들을 병합해서 새로운 연결 리스트로 만들어야 합니다. 물론 이 새로운 연결 리스트도 오름차순으로 정렬되야 합니다.

떠오르는 방법이 있나요?

우선 모든 연결 리스트들의 값을 알아야 하기 때문에 순회를 해야 합니다. 순회를 해서 노드 값이 작은 순으로 새로운 연결 리스트로 만들어야 합니다.

자료 구조를 생각해보겠습니다. 이런것들을 저장, 관리할 수 있는 자료 구조가 있을까요?

바로 우선순위 큐입니다.

우선 순위 큐에 연결리스트들의 모든 노드 값을 저장하고 큐에서 꺼낼때마다 노드 값이 작은 값을 가져와서 새로운 연결 리스트에 연결하면 되지 않을까요?

우선 순위 큐는 힙으로 구성되어있고, 위 조건을 만족하기 위해선 최소힙을 사용하면 됩니다!!

힙에서 값을 enqueue, dequeue 모두 log 값의 시간 복잡도가 나오게 됩니다.

힙 자료구조에 값을 넣을때는 연결 리스트의 현재 노드와 연결 리스트를 넣어야 합니다. 왜냐하면 현재 노드는 우선 순위를 결정하고, 연결 리스트는 우선 순위를 결정하는데 사용되는 노드의 next노드를 파악해야 하기 때문입니다.

그렇다면 시간 복잡도는 $O(logk)$ 가 될 것이며, 모든 노드에 진행되기 때문에 총 $O(nlogk)$ 의 시간 복잡도로 구성할 수 있습니다.

또 다른 방법이 있을까요?

이 문제는 주어진 연결 리스트들을 병합하는 것입니다. 바로 분할 정복 알고리즘을 사용할 수 있습니다.

최소개의 리스트(연결 리스트)로 나눈다음 나눈것들끼리 정렬하고 다시 합쳐서 정렬하는 분할 정복입니다. 해당 문제는 각 연결 리스트들은 정렬이 되어있기 때문에 나눈 다음 합칠 때 마다 정렬 과정을 거치면 됩니다.

분할 정복도 마찬가지로 O(nlogk)의 시간 복잡도로 구성이 가능합니다.

그럼 코드 설계를 해볼까요?

Step3. 코드 설계

우선 순위 큐를 이용한 방식

초기화:
- 최소 힙 자료구조를 사용하여 각 연결 리스트의 첫 번째 노드의 값을 힙에 삽입합니다. 힙에는 (노드 값, 리스트 인덱스, 노드) 형태로 저장하여 노드 값이 같은 경우에도 리스트 인덱스를 기준으로 순서를 보장합니다.
힙을 통해 병합:
- 힙에서 가장 작은 값을 가진 노드를 꺼내어 결과 연결 리스트에 추가합니다.
- 꺼낸 노드가 속한 연결 리스트의 다음 노드를 힙에 삽입합니다.
연결 리스트 반환:
- 힙이 빌 때까지 위 과정을 반복하여 병합된 연결 리스트를 반환합니다.

분할 정복을 이용한 방식

분할:
- 주어진 연결 리스트를 중간 지점에서 두 그룹으로 나누어 재귀적으로 병합 작업을 수행합니다.
정복:
- 나눠진 각 그룹을 병합합니다. 두 개의 연결 리스트를 병합하는 과정은 mergeTwoLists 함수를 사용합니다.
- 두 연결 리스트를 비교하여 값을 오름차순으로 정렬하며 새로운 리스트를 구성합니다.
종료 조건:
- 리스트가 하나 또는 비어있으면 그대로 반환합니다.

Step4. 코드 구현

우선 순위 큐

from heapq import heappop, heappush
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    # # 1. 우선순위 큐
    def mergeKLists(self, lists):
        # https://leetcode.com/problems/merge-k-sorted-lists/submissions/1471587504
        """
        :type lists: List[Optional[ListNode]]
        :rtype: Optional[ListNode]
        """
        
        if not lists or len(lists) == 0:
            return None
        
        heap = []

        for i, l in lists:
            # l : type Optional[ListNode]
            if l:
                heappush(heap,(l.val, i, l))
        dummy = ListNode()
        current = dummy

        while heap:
            val, i, node = heappop(heap)
            current.next = node
            current = current.next
            if node.next:
                heappush(heap,(node.next.val, i, node.next))
        return dummy.next

코드 설명:
- heapq를 사용해 연결 리스트를 최소값 기준으로 정렬하며 병합합니다.
- 힙에 (노드 값, 리스트 인덱스, 노드)를 저장해 동일 값일 때도 정렬이 가능합니다.
- 결과 연결 리스트는 dummy 노드를 사용하여 생성됩니다.
시간 복잡도:
- 각 노드에 대해 힙 연산이 발생하므로 $O(nlogk)$ , 여기서 n은 전체 노드 수, k는 연결 리스트 개수.
결과: https://leetcode.com/problems/merge-k-sorted-lists/submissions/1471587504

분할 정복

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
# 2. 분할 정복
    def mergeKLists(self, lists):
        # https://leetcode.com/problems/merge-k-sorted-lists/submissions/1471581479
        """
        :type lists: List[Optional[ListNode]]
        :rtype: Optional[ListNode]
        """
        if not lists or len(lists) == 0:
            return None
        if len(lists) == 1:
            return lists[0]
        
        mid = len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.mergeTwoLists(left, right)
        

    def mergeTwoLists(self,l1, l2): # 두 리스트를 병합하는 작업
        if not l1 or not l2:
            return l1 or l2

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

코드 설명:
- mergeKLists는 연결 리스트를 분할한 후, 병합하며 재귀적으로 호출됩니다.
- mergeTwoLists는 두 연결 리스트를 병합하는 재귀 함수로, 작은 값을 가진 노드를 선택해 새로운 연결 리스트를 구성합니다.
시간 복잡도:
- $O(nlog⁡k)$ : 분할 정복 과정에서 리스트를 나누는 데 $O(logk)$ , 병합하는 데 $O(n)$ 이 소요됩니다.
결과: https://leetcode.com/problems/merge-k-sorted-lists/submissions/1471581479

4. 마무리

이번 문제는 연결 리스트를 병합하는 고난도 문제로, 우선 순위 큐와 분할 정복 두 가지 방법으로 해결할 수 있었습니다.

우선 순위 큐:
- 힙 자료구조를 이용해 효율적으로 가장 작은 노드를 선택하며 병합했습니다.
- 힙의 특성을 활용해 O(logk) 시간 복잡도로 노드를 처리했습니다.
분할 정복:
- 연결 리스트를 반으로 나눠 병합하는 작업을 반복하며 문제를 해결했습니다.
- 재귀적으로 병합하여 O(logk)의 깊이를 가지며 각 병합 작업은 O(n) 시간이 소요됩니다.

선택 기준: