[ leetcode 문제풀이 ] Merge K Sorted Lists

Merge k Sorted Lists - LeetCode

Merge k Sorted Lists - LeetCode

(Merge K Sorted Lists 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Merge K Sorted Lists 문제 설명 >

 

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 lists lists가 주어질 때, 모든 linked lists를 하나의 정렬된 linked list로 합병한 후 이를 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 다음과 같다:

k == lists.length0  ≤  k  ≤  10^40  ≤  lists[i].length  ≤  500-10^4  ≤ lists[i][j]  ≤ 10^4lists[i]는 순증가하는 순서로 정렬되어 있다.lists[i].length의 합은 10^4을 넘지 않는다.

 

 

 

---

< Merge K Sorted Lists 문제 접근 >

 

이 문제는 Merge Two Sorted Lists의 일반화 버전이다. 하지만, Merge Two Sorted Lists의 방식처럼 lists의 head 중 가장 작은 값을 골라 tail에 연결하는 것을 반복적으로 실행하면 time limit exceed를 맞이하고 만다. 

 

따라서, 이 문제의 경우 related topics로 있는 Heap (Priority Queue)를 사용해주어야 한다. 이를 위해 cpp의 stl(algorithm header)에서 제공하는 make_heap, pop_heap, push_heap 함수를 사용하였다. (이들은 임의 접근 가능한 컨테이너에 대해 위 함수를 제공→ vector 컨테이너에 적용 가능!)

 

 

구체적으로 작성한 코드를 보자. (Cpp 사용)

 

#include <algorithm>

static bool sort_cmp(ListNode* list1, ListNode* list2){
    if(list1 == nullptr) return false;
    if(list2 == nullptr) return true;
    return list1->val < list2->val;
}
static bool heap_cmp(ListNode* list1, ListNode* list2){
    return list1->val > list2->val;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    if(lists.size() == 0) return nullptr;

    // sort_cmp를 통해 lists의 empty list를 모두 제거
    sort(lists.begin(), lists.end(), sort_cmp);
    for(int i=0;i<lists.size();i++)
        if(lists[i] == nullptr){
            lists.erase(lists.begin()+i, lists.end());
            break;
        } 
    if(lists.size() == 0) return nullptr;
        
    // head와 tail 초기화 및 heapify
    pop_heap(lists.begin(), lists.end(), heap_cmp);
    ListNode *head = lists.back(), *tail = lists.back();
    
    lists.back() = lists.back()->next;
    if(lists.back() == nullptr) lists.pop_back();
    make_heap(lists.begin(), lists.end(), heap_cmp);
     
    while(lists.size() > 1){
        pop_heap(lists.begin(), lists.end(), heap_cmp);
        tail->next = lists.back();
        tail = tail->next;
            
        lists.back() = lists.back()->next;
        if(lists.back() == nullptr) lists.pop_back();
        else push_heap(lists.begin(), lists.end(), heap_cmp);
    }
    tail->next = lists[0];
        
    return head;
} // runtime : 24 ms (faster than 84.15 %), memory usage : 13.1 MB (less than 84.88 %)​

 

구체적인 코드에 대한 설명은 다음과 같다.

 

void make_heap( RandomIt first, RandomIt last, Compare comp );

→ vector의 [first, last)에 대해 comp라는 비교함수로 heapify한다. 이때, comp 비교함수- The element with the highest value is an element for which this would return false when compared to every other element in the range.(가장 우선순위가 높은 element는 다른 모든 element와의 비교에서 모두 false를 리턴하는 element임)

위 정의가 의미하는 바는 make_heap는 default로 max heap를 구성한다는 점에서 알 수 있는데, 일반적으로 cmp를 a < b라 했을 때 cmp가 false가 된다는 말은 a > b, 즉 a가 b보다 우선순위를 갖는다는 것이다. 내림차순 정렬한다는 것 ! 이를 이용해 heap_cmp 함수를 작성하였다.

(sort는 오름차순 정렬이라 true 가 우선인데, 이를 이용해 empty list를 제거하는 cmp 함수를 작성하였다.)

 

void pop_heap( RandomIt first, RandomIt last, Compare comp );

→ pop_heap함수는 heap의 root node를 vector의 마지막 위치로 이동시키는 operation을 한다. (이는 삭제 operation인 vector.pop_back()와 함께 사용하기 위함)

 

void push_heap( RandomIt first, RandomIt last, Compare comp );

→ vector.push_back()을 한 후 push_heap()을 실행해주면 heap에 원소를 삽입하는 operation을 진행한다.

 

 

Time Complexity Analysis : k == lists.length, n = sum(lists[i].length)라 하면

[ sorting- O(k log k) ] + [ make heap - O(k) ] + [while loop - O(n) * push heap - O(log k)]

= O(n log k) ≤ O(n log n)

Space Complexity Analysis: O(1) (head, tail, for loop variable)

 

알고리즘 초기의 sorting이 시간을 너무 잡아먹는 것이 아닌가 싶었지만 time complexity 상으로는 sorting이 전체 알고리즘의 runtime을 지배하거나 하지는 않는 것으로 보인다.