Intuition

이미 정렬되어 있는 배열을 합쳐서 다시 정렬시킨다는 상황자체가 Merge Sort의 후반부 과정과 유사한 상황이다. 그러나 코드를 조금 더 직관적으로 작성하기 위해 두 개씩 배열을 비교하는 병합 정렬과 달리, 한번에 모든 배열을 비교하는 방식을 채택하기로 했다.

Approach

Merge Sort의 경우 두 개의 배열에 각각 포인터를 두고 값을 비교하며 더 작은 것을 새로운 정답 list에 담는다. 이후 작은 것이 나왔던 배열의 포인터를 뒤로 물러준다.

By CC BY-SA 3.0, Link

지금 하고자 하는 풀이는 위 방식에서 여러개의 배열을 한번에 본다는 차이점이 있다.

linkedList의 head 포인터와 그때그때 나오는 원소들을 가리킬 cur 포인터를 초기화시켜준다.

    listnode* head, *cur;
    head=cur=0;

최솟값을 담을 변수와 해당 인덱스를 담을 변수를 초기화시켜주고, 모든 배열을 순회하며 최솟값을 찾아낸다

while(1){
        int minIdx=-1, min=10001;
        for (int i=0;i<listsSize;i++){
            if (lists[i]&&lists[i]->val<min){ // lists[i]가 NULL인지 먼저 판단해야 heap overflow를 예방할 수 있음
                minIdx=i;
                min=lists[i]->val;
            }
        }
        ...
}

최초로 최솟값을 찾았다면 head와 cur 포인터를 먼저 설정시켜주어야 한다. 이후부터는 cur 포인터의 next를 최솟값 노드로 설정해주면 된다. 이후 cur 포인터를 방금 찾은 최솟값노드를 가리키게 만들어준다.

        if (!head) head=cur=lists[minIdx];
        else{
            cur->next=lists[minIdx];
            cur=cur->next;
        }

최솟값으로 판정된 node를 다음 node로 옮겨준다.

        lists[minIdx]=lists[minIdx]->next;

이 일련의 과정들은 더이상 확인할 배열이 없을때까지 반복된다.

    while(1){
        int minIdx=-1, min=10001;
        for (int i=0;i<listsSize;i++){
            if (lists[i]&&lists[i]->val<min){
                minIdx=i;
                min=lists[i]->val;
            }
        }

        if (minIdx==-1) break; // 더 이상 원소가 없다면 minIdx의 값은 초기화한 값에서 변경되지 않는다.

        if (!head) head=cur=lists[minIdx];
        else{
            cur->next=lists[minIdx];
            cur=cur->next;
        }

        lists[minIdx]=lists[minIdx]->next;
    }

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode listnode;

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    listnode* head, *cur;
    head=cur=0;

    while(1){
        int minIdx=-1, min=10001;
        for (int i=0;i<listsSize;i++){
            if (lists[i]&&lists[i]->val<min){
                minIdx=i;
                min=lists[i]->val;
            }
        }

        if (minIdx==-1) break;

        if (!head) head=cur=lists[minIdx];
        else{
            cur->next=lists[minIdx];
            cur=cur->next;
        }

        lists[minIdx]=lists[minIdx]->next;
    }

    return head;
}

Complexity

Time Complexity

linkedList내에 node가 1개씩 있다고 가정하게되면 매번 최솟값을 찾을때마다 $O(N)$이 발생하여 최종적으로 $O(N^2)$이 된다.

+번외) linkedList내에 node의 수가 충분하고 그에 따라 listsSize의 숫자가 작아지게 되면 훨씬 빠르게 작동할 수 있다. 예를 들어, $n$개의 원소들이 하나의 linkedList에 $n\over{10}$개씩, listsSize가 $10$이라 가정해보자. 이 경우 $10$번 순회하게 되면 최솟값 $1$개가 도출된다. 즉, $10n$번 순회하게 되면 최솟값 $n$개가 도출되고 $\Omega(N)$이 된다.

Space Complexity

추가적인 공간은 필요하지 않으므로 $O(N)$.

지적 및 질문 환영