문제

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.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

풀이

class Solution:
    def mergeKLists(self, lists):
        arr = []
        for nlist in lists:
            #리스트를 돌면서 arr에 넣어줌
            while nlist:
                arr.append(nlist.val)
                nlist = nlist.next
        
        #헤드와 현재 노드
        head = curr = None
        
        for val in sorted(arr):
            #처음
            if not curr:
                head = curr = ListNode(val)
            #연결시키기
            else:
                curr.next = ListNode(val)
                curr = curr.next
        
        return head

과정

간단하게 브루트포스 알고리즘을 쓴다.
리스트들을 돌면서 arr 에 넣어주고
arr를 sorted 한 val로 연결리스트들을 새로 만들어서 head를 리턴한다.

시간복잡도는 O(nlogn)이라고 한다...
우선순위 큐를 사용하면 최소값을 다룰 수 있기 때문에 이 문제에 대한 최적해라고 한다.

느낀점

이 문제를 C99로 풀려했더니 머리가 터질 뻔 했다. 파이썬으로 하면 이렇게 간단한 건데..뭔가 잘못된 게 아닐까?라는 생각까지..ㅋㅋㅋ
C99는 lists를

struct ListNode* (struct ListNode **lists, int listSize);

이렇게 선언을 하고 시작하니 거기에 이중포인터에 인덱스를 매겨서 다루는 광경을 봤다. 왜 **lists 일까..? 며칠을 고민하고 있네..그래도 이중포인터에 대해 공부를 많이 할 수 있는 계기가 되었다.
재밌다..?? 어렵다..? 둘다..? 그냥 하자