LeetCode - Merge k Sorted Lists

wodnr_P·2023년 10월 12일

Merge k Sorted Lists divide & conquer leetcode linked list 알고리즘

LeetCode Top Interview 150

목록 보기

30/32

⭐️ LeetCode 알고리즘 풀이 (with Python)

# Merge k Sorted Lists

[Quetion]

LeetCode 23. Merge k Sorted Lists

📌 접근법

[문제 이해]

이중 리스트 구조로 된 연결 리스트를 모두 합치고, 오름차순 정렬된 연결 리스트로 반환

[[1,4,5],[1,3,4],[2,6]]로 이루어진 연결리스트를 1->1->2->3->4->4->5->6로 반환 해야하는 문제이다.
가장 먼저 떠올린 접근방법은 다음과 같다.

포인터를 이동하며 이중 리스트 구조에 접근
연결 리스트의 값을 배열에 저장
값이 저장된 배열을 sorted()로 정렬
정렬된 배열을 기준으로 연결 리스트 생성

💻 구현

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 연결 리스트의 값 저장
        link=[]
        # 이중 리스트에 접근할 포인터
        i=0
        while len(lists)-1 >= i:
            if lists[i]:
                link.append(lists[i].val)
            else:
                i+=1
                continue
            lists[i]=lists[i].next
        
        # O(N log N) 정렬
        link=sorted(link)
        
        # 연결 리스트 생성
        result=ListNode()
        curr=result
        for i in link:
            node=ListNode(i)
            curr.next=node
            curr=node
        return result.next

Runtime: 75ms | Memory: 19.8MB
LeetCode 코드 중 Runtime 99%, Memory 81% 해당하는 결과

📌 로직 핵심

lists = [[1,4,5],[1,3,4],[2,6]]일때, i 포인터로 lists[i]에 접근 ex)(lists[0]=[1,4,5])
lists[i].next로 1->4->5 접근, 만약 lists[i]가 None일 경우, i 포인터의 값 증가 = 다음 리스트를 가리키고 다시 다음 리스트의 첫 값을 가리키도록 continue로 반복문 제어
병합 정렬 기반 sorted()함수로 오름차순 정렬
정렬된 리스트로 새로운 연결 리스트 생성

📝 Merge k Sorted Lists 회고

시간복잡도는 이중 연결리스트의 모든 값을 조회하므로 O(N)이 되고, 처음 연결 리스트의 값 개수 만큼 다시 새로운 연결 리스트를 생성하므로 O(N)의 공간복잡도를 가진다.
이중 리스트 구조에서 첫번째 리스트를 첫번째 하위 연결 리스트로 생각한다면, 재귀와 분할정복의 개념으로도 문제를 해결할 수 있을 것 같다. 하지만 성능적으로 봤을 때는 비슷하게 나올거라 예상된다.
문제 해결 후 솔루션을 확인해보니 heap 자료구조를 활용해서 문제를 해결할 수도 있었고, 코드는 더 간결하지만 현재 사용한 접근법과 유사한 방법으로 해결한 문제도 꽤 많았다.
추가적으로 연결 리스트를 생성하고, 서로 연결해주는 과정을 조금 더 간단하게 개선해보았다.

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        link=[]
        i=0
        while len(lists)-1 >= i:
            if lists[i]:
                link.append(lists[i].val)
            else:
                i+=1
                continue
            lists[i]=lists[i].next
            
        link=sorted(link, reverse=True)
        result=None
        for i in link:
            result=ListNode(i, result)
        return result