[Leetcode] 23. Merge k Sorted Lists_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '23. Merge k Sorted Lists'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Merge k Sorted Lists' 알고리즘 문제

 

STEP 2. 'Merge k Sorted Lists' 코드(code)

 

STEP 3. 'Merge k Sorted Lists' 해설

 

STEP 4. 'Merge k Sorted Lists' solution

 

반응형

 

STEP 1. 'Merge k Sorted Lists' 알고리즘 문제

 

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

 

각각의 연결 리스트가 오름차순으로 연결된 길이 k인 *연결 리스트가 주어집니다.

각각의 연결 리스트를 묶어서, 하나의 오름차순으로 정렬된 연결 리스트를 반환하면 됩니다.

 

* Linked list : 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조

---

STEP 2. 'Merge k Sorted Lists' 코드(code)

 

■ Runtime: 105 ms, Beats 76.67%
■ Memory: 20.9 MB, Beats 11.33%

 

# 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]:
        temp_lst = list()

        # Loop in lists.length
        for index in lists:
            # While lists.next is not None
            while index:
                temp_lst.append(index.val)
                index = index.next

        return_lst = sorted(temp_lst, reverse = True)

        # Create a ListNode from list
        final = None
        for value in return_lst:
            final = ListNode(value, final)

        return final

---

STEP 3. 'Merge k Sorted Lists' 해설

 

연결 리스트(Linked-list)를 하나의 리스트로 묶어주고, 이를 sorted 함수를 통해 오름 차순으로 정렬합니다.

그리고 최종적으로 반환될 형태가 연결 리스트이기에, ListNode class를 이용해 연결 리스트로 만들어서 return 했습니다.

 

 

STEP 4. 'Merge k Sorted Lists' solution

 

추가적으로, solution으로 공개된 코드를 살펴봤습니다. List → 정렬, sort → List로 유사한 방식으로 문제를 접근한 것을 확인했습니다.

 

■ Runtime: 113 ms Beats 58.16%
■ Beats: 20.7 MB Beats 14.73%

 

# 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]:
        new=[]
        for i in lists:
            while(i):
                new.append(i.val)
                i=i.next
        a=sorted(new)[::-1]
        final=None
        for i in a:
            final=ListNode(i,final)
        return final

 

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '23. Merge k Sorted Lists'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.