LeetCode

LeetCode 23 Merge k Sorted Lists 풀이: 최소 힙으로 k개 연결 리스트 병합

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

정렬된 연결 리스트가 여러 개 주어질 때 매 순간 전체 리스트의 최솟값을 효율적으로 찾아야 한다. 연결 리스트의 포인터를 직접 병합하면서 최소 힙의 동률 처리까지 고려해야 하므로 Level 3으로 판단했다.

1. 문제 요약

오름차순으로 정렬된 k개의 단일 연결 리스트가 주어진다. 모든 리스트의 노드를 하나의 오름차순 연결 리스트로 병합하고 그 시작 노드를 반환한다.

중요한 조건은 다음과 같다.

  • lists의 길이 k는 0 이상 10^4 이하이다.
  • 각 리스트의 길이는 최대 500이다.
  • 모든 리스트의 전체 노드 수를 합한 N은 10^4 이하이다.
  • 각 리스트는 오름차순으로 정렬되어 있다.
  • 노드 값은 -10^4 이상 10^4 이하이다.
  • 빈 리스트와 같은 값의 노드가 포함될 수 있다.

예를 들어 [1,4,5], [1,3,4], [2,6]을 병합하면 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6이 된다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

연결 리스트 구조와 최소 힙 상태

각 리스트의 아직 사용하지 않은 첫 번째 노드만 보면 된다. 각 리스트가 정렬되어 있으므로 한 리스트의 현재 노드보다 뒤에 있는 노드는 현재 노드보다 작을 수 없다.

그래서 최소 힙에는 각 리스트의 현재 노드, 즉 최대 k개의 후보만 저장한다. 힙의 최솟값을 꺼내 결과 리스트 뒤에 연결한 뒤, 그 노드가 속했던 리스트의 다음 노드를 힙에 넣는다.

힙: 각 리스트의 현재 head
     [1(list 1), 1(list 2), 2(list 3)]

1(list 1)을 꺼냄
결과: 1
힙에 list 1의 다음 노드 4를 추가

각 리스트의 현재 head만 후보로 두는 이유

현재 각 리스트의 첫 노드 중 최솟값은 전체 병합 결과에서 다음에 와야 하는 노드다. 선택하지 않은 리스트의 뒤쪽 노드는 그 리스트의 첫 노드보다 작지 않고, 다른 리스트도 현재 힙에 후보가 있으므로 힙의 최솟값보다 앞에 올 수 없다.

이 선택을 반복하면 모든 노드가 한 번씩 결과에 들어간다. 한 리스트에서 노드를 하나 꺼냈을 때는 그 리스트의 다음 노드만 새로운 후보가 되므로 힙 크기는 최대 k로 유지된다.

동률 값과 힙 원소 비교

Python의 heapq에 (node.val, node)를 넣으면 값이 같은 순간 두 번째 원소인 ListNode를 서로 비교하려고 할 수 있다. ListNode에는 기본 대소 비교가 없으므로 TypeError가 발생할 수 있다.

이를 피하기 위해 (node.val, sequence, node) 형태로 저장한다. sequence는 힙에 넣을 때마다 증가하는 고유 순번이므로 값이 같아도 Python은 순번만 비교하고 노드 객체까지 비교하지 않는다. 같은 값을 가진 노드도 중복 제거하지 않고 각각 결과에 포함해야 한다.

시간·공간 복잡도

전체 노드 수를 N, 리스트 수를 k라고 하자. 각 노드는 힙에 한 번 들어가고 한 번 나오며 힙 연산은 O(log k)이므로 시간 복잡도는 O(N log k)다. 힙에는 각 리스트의 현재 후보만 저장하므로 보조 공간 복잡도는 O(k)다. 결과는 기존 노드를 재사용해 구성하므로 새로운 노드 저장 공간은 별도로 필요하지 않다.

3. 문제 해결 코드 (Python)

각 리스트의 첫 노드를 최소 힙에 넣고, 최솟값 노드를 꺼낼 때마다 결과의 tail에 연결한다. 꺼낸 노드에 다음 노드가 있으면 같은 리스트의 다음 후보로 힙에 추가한다.

import heapq
from itertools import count


class Solution:
    def mergeKLists(self, lists: list['ListNode | None']) -> 'ListNode | None':
        min_heap = []
        sequence = count()

        for node in lists:
            if node is not None:
                heapq.heappush(min_heap, (node.val, next(sequence), node))

        dummy = ListNode(0)
        tail = dummy

        while min_heap:
            _, _, node = heapq.heappop(min_heap)

            if node.next is not None:
                heapq.heappush(min_heap, (node.next.val, next(sequence), node.next))

            tail.next = node
            tail = node

        tail.next = None
        return dummy.next

dummy는 결과 리스트의 첫 노드를 별도로 처리하지 않기 위한 임시 노드다. sequence는 노드 값이 같은 경우에도 힙 원소의 비교 순서를 결정해 ListNode 객체 비교를 방지한다. 기존 노드를 tail.next에 연결하므로 모든 리스트를 값 배열로 복사하거나 새 노드를 만들지 않는다.

4. 오답 접근과 반례

매번 모든 리스트의 head를 순회하기

현재 노드가 남아 있는 모든 리스트를 매번 확인해 최솟값을 찾으면 구현은 쉽지만, 각 결과 노드를 만들 때마다 최대 k개의 head를 확인해야 한다.

k = 3, 전체 노드 수 N = 8
각 노드를 선택할 때마다 세 리스트의 현재 head를 비교

이 방식은 시간 복잡도가 O(Nk)가 되어 k가 커질수록 비효율적이다. 최소 힙은 후보를 O(log k)에 갱신한다.

모든 값을 배열에 모아 정렬하기

모든 노드 값을 배열로 복사한 뒤 정렬하면 결과는 얻을 수 있지만, 이미 각 리스트가 정렬되어 있다는 정보를 충분히 사용하지 못한다. 전체 노드가 N개이면 정렬에 O(N log N) 시간이 필요하고, 값 배열을 위한 O(N) 공간도 추가된다.

값만 힙에 저장하기

값만 저장해 정렬된 값을 만들면 어떤 연결 리스트의 다음 노드를 가져와야 하는지 알 수 없고, 원래 노드 연결을 재사용할 수도 없다. 힙에는 값과 함께 실제 ListNode를 저장해야 한다.

같은 값의 노드를 직접 비교하게 만들기

다음과 같이 값과 노드만 튜플에 넣으면 같은 값에서 ListNode 비교 오류가 발생할 수 있다.

heapq.heappush(min_heap, (node.val, node))  # 같은 값에서 비교 오류 가능

고유 순번을 중간에 넣어 (값, 순번, 노드)로 만들면 같은 값도 안전하게 처리할 수 있다.

복사해 실행할 테스트

로컬 실행에서는 아래 ListNode와 헬퍼를 풀이 클래스 앞에 두고, 검증 코드를 클래스 뒤에 붙여 실행한다.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def make_list(values):
    dummy = tail = ListNode()
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next

def to_list(node):
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result

merged = Solution().mergeKLists([make_list([1, 4, 5]), make_list([1, 3, 4]), make_list([2, 6])])
assert to_list(merged) == [1, 1, 2, 3, 4, 4, 5, 6]
assert Solution().mergeKLists([]) is None

5. 공식 예제와 추가 검증

작성한 mergeKLists 함수를 Python에서 직접 연결 리스트 노드로 구성해 공식 예제와 경계 사례를 확인했다. 반환 리스트의 값 순서와 동일한 값이 여러 리스트에 있는 경우를 함께 확인했다.

공식 예제

입력: lists = [[1,4,5], [1,3,4], [2,6]]
기대 출력: [1,1,2,3,4,4,5,6]
확인 결과: 통과
검증 목적: 여러 정렬 리스트의 기본 병합 확인
입력: lists = []
기대 출력: []
확인 결과: 통과
검증 목적: 리스트 배열 자체가 비어 있는 경우 확인
입력: lists = [[]]
기대 출력: []
확인 결과: 통과
검증 목적: 빈 연결 리스트만 포함된 경우 확인

추가 검증 1: 같은 값이 여러 리스트에 있는 경우

입력: lists = [[1,1], [1], [1,2]]
기대 출력: [1,1,1,1,2]
확인 결과: 통과
검증 목적: 동일한 값의 ListNode를 비교 오류 없이 모두 병합하는지 확인

추가 검증 2: 음수와 길이가 다른 리스트

입력: lists = [[-10,-3,7], [-8,-3,2,9], []]
기대 출력: [-10,-8,-3,-3,2,7,9]
확인 결과: 통과
검증 목적: 음수, 빈 리스트, 길이가 다른 리스트를 함께 처리하는지 확인

추가 검증 3: 리스트 하나

입력: lists = [[-2,0,5]]
기대 출력: [-2,0,5]
확인 결과: 통과
검증 목적: 병합할 리스트가 하나일 때 기존 연결을 유지하는지 확인

6. 다른 풀이 방식 검색 및 비교

모든 값을 배열에 모아 정렬하는 방법은 구현이 가장 단순하지만 O(N log N) 시간과 O(N) 공간이 필요하다. 리스트를 두 개씩 순차 병합하면 추가 공간은 적지만 앞에서 합쳐진 리스트를 반복해서 순회해 O(Nk) 시간이 될 수 있다.

분할 정복으로 리스트를 비슷한 크기의 그룹끼리 병합하면 O(N log k) 시간에 해결할 수 있다. 이 글의 최소 힙 방식은 현재 k개 후보 중 최솟값을 직접 관리하며, 각 단계의 선택 과정을 설명하기 쉽고 O(N log k) 시간과 O(k) 공간을 사용한다.

마무리

Merge k Sorted Lists는 각 정렬 리스트의 현재 head 중 최솟값만 다음 결과 노드가 될 수 있다는 점을 이용하는 문제다. 각 리스트의 현재 노드를 최소 힙에 넣고, 노드를 꺼낼 때 그 다음 노드를 추가하면 전체 노드를 정렬된 순서로 연결할 수 있다. 동일한 값의 노드도 고유 순번과 함께 힙에 저장하면 O(N log k) 시간에 안전하게 처리할 수 있다.

#힙#LeetCode#난이도 3