[75 LeetCode] 10 - Merge K Sorted List

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/merge-k-sorted-lists/description/

Merge k Sorted Lists - LeetCode

 

잘 없던 난이도 Hard 문제다.

k개의 정렬된 Linked List를 입력받아, 정렬된 하나의 Linked List로 만들어야한다.

처음에는 그냥 item을 다 뽑아서 sort 후 Linked List로 만들어줬다.
(O(N + Nlog(N) + N) = O(N*log(N)) (N개의 리스트노드를 정렬하는 것과 같다.)

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (!lists.length) return null;

  const arr: number[] = [];
  let cur: null | ListNode = null;

  lists.forEach(node => {
      while (node) {
          arr.push(node.val);
          node = node.next;
      }
  });

  arr.sort((a, b) => a - b);

  for( let i = arr.length - 1; i >= 0; i--) {
      const newNode = { val: arr[i], next: cur };
      cur = newNode;
  }

  return cur;
};

그 후 문제 분류가 힙이길래 힙으로 시도해봤는데, 힙이 오히려 더 느렸다.

solution에 있는 방식의 heap 알고리즘을 사용했다. 

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (!lists.length) return null;

  const heap = new Heap();
  let prev: null | ListNode = null;
  let head: null | ListNode = null;

  lists.forEach((node) => {
    node && heap.push(node);
  });

  while (!heap.isEmpty()) {
    const node = heap.pop();

    if (node.next) heap.push({ ...node.next });

    const newNode = { val: node.val, next: null };
    if (prev) {
      prev.next = newNode;
    }
    prev = newNode;

    if (!head) {
      head = prev;
    }
  }

  return head;
}

1. 각 Linked List의 현재 head를 heap에 넣는다.
2. heap이 빌 때 까지
   1. heap에서 하나를 뽑아 새 Linked List에 붙여주고
   2. heap에 뽑은 노드의 다음 노드가 있다면 넣어준다.

O(k + N*(logk)) = O(Nlogk)
Comparison cost가 heap을 사용했기 때문에 logk까지 줄어든 것을 알 수 있다.

하지만 실제로는 구현상의 문제나 GC가 오래 걸려 이게 더 느린 것 같다.

chat gpt에게 질문한 결과로 돌려봐도 느린건 마찬가지였다.

 

추가) 힙구현

class Heap {
  instance = Array(5000001);
  size: number = 0;

  push(val: ListNode) {
    this.size += 1;
    this.instance[this.size] = val;
    let index = this.size;

    while (index > 1) {
      const parent = Math.floor(index / 2);
      if (this.instance[index].val < this.instance[parent].val) {
        const tmp = this.instance[index];
        this.instance[index] = this.instance[parent];
        this.instance[parent] = tmp;

        index = parent;
      } else {
        return;
      }
    }
  }

  pop() {
    const ret = this.instance[1];
    const last = this.instance[this.size];
    this.size -= 1;
    this.instance[1] = last;

    if (this.size) this.minHeapify(1);

    return ret;
  }

  minHeapify(root: number) {
    let min = this.instance[root]?.val;
    let minIdx = root;
    let left = root * 2;
    let right = root * 2 + 1;

    if (right <= this.size && this.instance[right].val < min) {
      min = this.instance[right].val;
      minIdx = right;
    }

    if (left <= this.size && this.instance[left].val < min) {
      min = this.instance[left].val;
      minIdx = left;
    }

    if (minIdx !== root) {
      const tmp = this.instance[minIdx];
      this.instance[minIdx] = this.instance[root];
      this.instance[root] = tmp;

      return this.minHeapify(minIdx);
    }
  }

  isEmpty() {
    return this.size === 0;
  }
}