[2021][01]Merge K sorted Lists

문제 정보

문제 요약

k 개의 오름차순으로 정렬된 연결 리스트의 리스트가 주어졌을 때 모든 연결 리스트를 하나의 연결리스트로 합치고 하나로 합쳐진 연결리스트를 반환하라.

제약사항

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^ 4
• lists[i]는 오름 차순으로 정렬되어 잇음
• 각 lists[i] 길이의 합은 10^4. 를 초과하지 않음

접근 방법

문제를 보고 처음에 생각한 방법은 lists[i]를 순회하면서 가장 작은 값의 ListNode를 찾고, 찾은 lists[i]의 포인터?라고 해야하나 현재 위치를 나타내는 ListNode의 위치를 next로 옮기고 이런 방식으로 하나로 합치는 방법을 생각했었음. 내가 생각했을 때 이 방식으로 풀기 어렵다고 생각한 것은 모든 list[i]에 대해서 최소 val을 가진 lists[i]를 찾는 게 어렵다고 생각했었음. Divide and Conquer 방식으로 푼 후에 다른 사람의 우선순위 큐를 활용한 풀이가 이 생각을 구체화한 풀이임.

Divide and Conquer 방식의 풀이는 이 풀이의 K개의 연결리스트가 주어진다고 하더라도 가장 기본적인 케이스는 2개의 연결리스트를 병합하는 것이라고 생각했음. 그래서 2 개의 연결리스트를 병합하는 함수를 만들고 이를 k개의 연결리스트에 대해서 실행하면 문제에서 원하는 결과를 반환할 수 있음.

from typing import List

# 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:

        def helper(l: ListNode, r: ListNode) -> ListNode:
        	# 2개의 오름차순 정렬된 연결리스트를 하나로 합치는 함수.
            answer = ListNode()
            res = answer
            curL = l
            curR = r
            while curL and curR:
                if curL.val > curR.val:
                    res.next = curR
                    res = res.next
                    curR = curR.next
                    continue
                else:
                    res.next = curL
                    res = res.next
                    curL = curL.next
                    continue

            if curL:
                res.next = curL

            if curR:
                res.next = curR

            return answer.next

        k = len(lists)
        # 시작할 때 처음 answer = None과 다음 연결리스트를 병합해서
        # answer에 그 병합된 결과를 반환하면 k개의 연결리스트를 병합한 결과를 얻을 수 있음.
        answer = None
        for i in range(k):
            answer = helper(answer, lists[i])
        return answer