[자료구조와 알고리즘] 148. Sort List (Feat. Merge Sort)

문제 설명

leetcode Top Interview 150 - 148. Sort List
head라는 linked list가 주어지면 이 리스트를 오름차순으로 정렬하는 문제입니다.
head는 ListNode라는 형태로 주어집니다.
이 구조가 익숙하지 않으시다면 Linked List 구현해보기를 참고해주세요.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

풀어보기

주어진 리스트를 재귀함수를 통해 풀어보았습니다.

/**
 * @param {ListNode} head
 * @return {ListNode}
 */


var sortList = function(head) {
     const temp = [];
  	 // 재귀함수로 탐색하면서 temp 배열에 각 노드의 val 저장
     function inputVal(node) {
          if (!node) return;
          temp.push(node.val);
          return inputVal(node.next);
     }
     inputVal(head);
     temp.sort((a,b)=>{return a-b});

     let i = 0;
  	 // 정렬된 temp 배열의 값을 순서대로 head 배열에 저장
     function setVal(node) {
          if (!node) return;
          node.val = temp[i++];
          return setVal(node.next);
     }
     setVal(head);
     return head;
};

제 코드는 temp라는 임시 배열을 생성하고 연산을 하기 때문에 공간 효율성이 좋지 못합니다..🥲

더 좋은 코드

이 문제를 Merge Sort 병합 정렬로 풀이하면 (제 코드보다는) 공간 효율성이 훨씬 좋아집니다!

이미지 출처: https://www.geeksforgeeks.org/merge-sort/
병합 정렬은 전체 배열을 쪼개서 정렬한 다음 다시 병합시키면서 정렬하는 배열로 어떤 순서의 배열이 주어지더라도 O(nlog₂n)의 시간 복잡도를 갖는 정렬 알고리즘입니다. Divide and Conquer 분할 정복 알고리즘 중의 하나입니다.
공간 효율성이 특히 좋은 알고리즘은 아니지만 스택이 쌓이는 재귀 함수를 이용한 제 방법보다는 효율적입니다. 😅

var sortList = function(head) {
    if (head === null || head.next === null) {
        return head;
    }
    //  1) 분할 정복 알고리즘의 첫 단계인 분할을 합니다.
    const [left, right] = split(head);
    // root : 최종적으로 정렬된 리스트를 연결시킬 루트 노드를 생성
    // merge 함수의 반환 값으로 root.next를 반환하므로 임시 노드입니다.
    const root = new ListNode(null);
  	// 2) 분할된 배열을 다시 병합시킵니다.
    return merge(root, sortList(left), sortList(right))
};

// 1) 분할 단계
function split(node) {
    let slow = node;
    let fast = node;
    // 토끼와 거북이 알고리즘으로 배열의 중간 노드를 찾습니다.
  	// 토끼 포인터가 없는 경우 거북이 포인터가 중간 노드에 도달했다고 볼 수 있습니다!
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    const left = node;
    const right = slow.next;
    // 거북이 포인터의 next를 비워줘야 left 배열과 right 배열을 분리할 수 있습니다.
    slow.next = null;
    
    return [left, right];
}

// 2) 병합 단계
function merge(root, left, right) {
    let pointer = root;
    // left 배열과 right 배열의 각 노드의 val 값을 비교하면서 더 작은 값을
    // root 배열 뒤에 연결시킵니다.
    while(left !== null || right !== null) {
        if (left === null) {
            pointer.next = right;
            right = right.next;
        } else if (right === null) {
            pointer.next = left;
            left = left.next;
        } else {
            if (left.val < right.val) {
                pointer.next = left;
                left = left.next;
            } else {
                pointer.next = right;
                right = right.next;
            }
        }
        pointer = pointer.next;
    }

    return root.next;
}

훨씬 좋아진 공간 복잡도.. 😇

마무리

문제를 풀 때 어떤 접근법으로 어떻게 복잡도를 낮출 수 있는 지 공부하면서 풀어야 겠습니다.