27. Merge k Sorted Lists

🎯 leetcode - 344. Reverse String

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 27번 문제

📌 날짜

2020.01.31

📌 시도 횟수

3 try

💡 Code 1 (시간초과 발생함)

class Solution:
    def mergeTwoLists(self, l1, l2):
        if (not l1) or (l2 and (l1.val > l2.val)):
            l1, l2 = l2, l1
        if l1:
            l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if lists is None:
            return None
        result = None
        for list in lists:
            result = self.mergeTwoLists(result, list)

        return result

💡 Code 2

class Solution:
    def list2node(self, list1: List):
        head = result_node = ListNode()
        for num in list1:
            result_node.next = ListNode(num)
            result_node = result_node.next
        return head.next

    def node2list(self, node1: ListNode):
        list1 = []
        while node1 != None:
            list1.append(node1.val)
            node1 = node1.next
        return list1

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if lists is None:
            return None
        result = []
        for list in lists:
            result += self.node2list(list)
        result.sort()

        return self.list2node(result)

💡 문제 해결 방법

✅ Code 1
- 14. Merge Two Sorted Lists에서 새로운 풀이 中 2번의 재귀 방법을 이용했다.
- k개의 리스트를 앞에서부터 2개씩 합쳐가면서 풀이하는 방식이다.
---------------- 예시 ----------------
>>> [1, 2, 3], [2, 4, 6], [5, 7, 9]
>>> [1, 2, 2, 3, 4, 6], [5, 7, 9]
>>> [1, 2, 2, 3, 4, 5, 6, 7, 9]
--------------------------------------

✅ Code 2
- 편법을 썼다ㅠ😅

🚀 게시물 다시보기 - 14. Merge Two Sorted Lists

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

💡 Code 1
- 시간초과가 발생했다.

---

😉 다른 풀이

📌 하나. heapq 이용하기

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        root = result = ListNode(None)
        heap = []
        # lists안의 각 연결리스트의 루트를 힙에 저장한다.
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i, lists[i]))

        # 힙 추출 후 추출한 힙의 다음 연결리스트가 있다면 다시 힙에 넣는다.
        while heap:
            node = heapq.heappop(heap)
            idx = node[1]
            result.next = node[2]

            result = result.next
            if result.next:
                heapq.heappush(heap, (result.next.val, idx, result.next))

        return root.next

문제 해결 방법

• lists안의 각 연결리스트의 루트를 힙에 저장한 결과는 아래와 같다 .
• 예시로 lists = [(1 → 3), (2 → 4)]를 입력값으로 넣어보았다.
• lists[0] = (1 → 3)의 첫번째 노드 1과 lists[1] = (2 → 4)의 첫번째 노드 2가 heap에 저장되었음을 볼 수 있다.

• 위의 코드에서 while문을 돌면서 가장 heap에 저장된 값 중 최소 값을 빼서 result.next에 한 개씩 연결한다.

• 즉 아래의 방법과 비슷하다.
• 단, 각 주머니 안의 구슬은 무조건 숫자가 작은 순서대로 한 개 씩 나올 수 있다.
  

---

...

💡 새롭게 알게 된 점

✔ heapq에 대해 새롭게 알게 되었다!
- heapq 모듈은 최소 힙을 지원한다. 
- 지정된 우선순위값이 작은 순서대로 값을 꺼낼 수 있다.
- heapq에서 값을 한개씩 꺼낼 때에는 heapq.heappop(heap)을 이용한다.
- heapq에 원소를 삽입할 때는 headq.heappush(우선순위값, (튜플))을 사용한다.
- 튜플 값이 이미 heap 안에 저장된 값과 중복되는 것은 삽입할 수 없다.
따라서 위의 코드에서는 index 값을 튜플의 추가 인자로 사용했다. 

+ 참고로 list를 바로 힙 정렬으로 만드는 heapq.heapfy(list) 함수도 있다.

---