[데크, 우선순위 큐] 27 k개 정렬 리스트 병합(Merge k Sorted Lists)

<LeetCode 문제>

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

Merge k Sorted Lists - LeetCode

k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하는 문제입니다.

<풀이>

먼저 연결리스트의 모든 값들을 리스트에 넣은 후 풀이하는 방법은 다음과 같습니다.

# 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]:
        nodes = [] #연결리스트의 값들만 nodes에 넣기
        for l in lists:
            while l:
                nodes.append(l.val)
                l= l.next
        
        head=point=ListNode(0) #맨앞에 dummy 두기
        for x in sorted(nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next #dummy 다음거부터

 

우선순위 큐를 이용하는 풀이는 다음과 같습니다.

# 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]:
        heap = [] #min heap으로 사용할 list
        
        head=point=ListNode(0) #맨앞에 dummy 두기
        for i in range(len(lists)):
            if lists[i]: #빈리스트인 경우 제외하기 위해
                heapq.heappush(heap,(lists[i].val,i,lists[i])) #i는 그저 에러방지용으로 같이
        
        #min heap에서 값 하나씩 뽑기
        while heap:
            node = heapq.heappop(heap) 
            idx = node[1] #에러방지용 값
            point.next = node[2] #linked list 정답에 연결
            point = point.next # 다음 next에 또 연결하기 위해 point 이동
            
            if point.next: #linked list에 연결된 다음 linked list가 있으면
                heapq.heappush(heap,(point.next.val,idx, point.next))
              
        return head.next #dummy 다음거부터

<학습내용>

1.

<학습이 필요한 내용>

1. (lists[i].val,i,lists[i])에서 i빼면 터지는 이유 찾기
2. 딕셔너리 디폴트 들어가는 순서 찾기