2021-01-24] Merge k Sorted Lists

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/582/week-4-january-22nd-january-28th/3615/

 

주어지는 2차원 배열에 값들을 하나의 정렬된 List 값으로 전달하는 문제이다.

 

예시를 보면 아래와 같다.

 

예시 1번처럼 값이 주어졌을때, 정렬된 List로 merge하여 하나의 List로 반환해준다.

예시 2,3번은 주어지는 값이 없을때에 대한 예외처리 를 보여주는 구간이다.

 

문제의 답을 도출하기 위해, 모든 데이터의 값을 한 List에 받은 후, sort 함수를 써서 정렬하면 값을 도출할 수 있다.

 

하지만, 형식이 List가 아닌 ListNode로, 모두 생성해주며 만들어줘야한다.

 

문제에서 요구하는 ListNode는 단방향이기 때문에, 값을 만들어 줄 때 반복할 필요 없이 마지막 값 부터 만들어

이 값이 next에 붙게 만들어 주면 성능이 좋아진다.

 

# 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:
        ans=[]
        if lists==[]:
            return None
        m=len(lists)
        if m==1 and lists[0]==None:
            return None
        ### 문제 2-3 번에 대한 예외 처리 ###
        for i in range(m):
            while lists[i]!=None:
                ans.append(lists[i].val) # 모든 값을 ans라는 List에 저장
                lists[i]=lists[i].next
        data=sorted(ans,reverse=True) # 저장된 값을 역순으로 재배열 
        if data==[]:
            return None # 혹시라도 없다면 None return
        last=ListNode(data[0])
        for d in data[1:]:
            last=ListNode(d,last) # 마지막 값을 next로 배치함으로 맨 처음값이 HEAD에 배치됨
        return last