[LeetCode] 725. Split Linked List in Parts

문제 출처: https://leetcode.com/problems/split-linked-list-in-parts/

Split Linked List in Parts - LeetCode

---

문제

단일 연결 리스트의 head와 정수 k가 주어지면, 연속으로 연결된 k개의 연결 리스트로 분리하라.

 

각 부분의 길이는 가능한 한 동일해야 한다: 어떤 두 부분도 크기가 1보다 크게 차이 나서는 안된다. 이러한 조건이 일부 부분에 null 값을 이끌 수도 있다.

 

각 부분은 입력 리스트에서 등장하는 순서여야 하고, 일찍 등장하는 부분이 그렇지 않은 부분보다 더 크거나 갖은 크기를 가져야 한다.

 

k개의 부분을 배열로 반환하라.

예제

Input: head = [1,2,3], k = 5
Output: [[1],[2],[3],[],[]]

Explanation:
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but its string representation as a ListNode is [].

Input: head = [1,2,3,4,5,6,7,8,9,10], k = 3
Output: [[1,2,3,4],[5,6,7],[8,9,10]]

Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

 

---

풀이

주어진 연결 리스트를 k개의 조각으로 나누기 위해서 우선적으로 필요한 정보가 연결리스트의 길이입니다. 연결리스트의 크기가 n이라 하면, $n \div k$의 몫과 나머지를 통해 한 부분에 몇개의 원소가 있어야 하는지 알 수 있습니다.

 

연결리스트의 길이를 알기 위해서 런너(Runner) 기법을 이용할 수 있습니다.

function getListLength(head) {
    let len = 0;
    
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
    	slow = slow.next;
        fast = fast.next.next;
    	len += 1;
    }
    len = 2 * len;
    if (fast) { len += 1; }
    
    return len;
}

런너 기법은 다음과 같은 두 개의 포인터를 사용하는 기법입니다.

• slow: 한 스텝당 1만큼 이동하는 포인터
• fast: 한 스텝당 2만큼 이동하는 포인터

이러한 방식으로 연결리스트를 탐색하게 되면, fast가 리스트의 끝, 더 이상 이동이 불가능한 위치에 가게 되면 slow는 리스트의 중간에 위치하게 됩니다. 이를 활용하여 slow가 이동한 수를 기반으로 전체 리스트 길이를 구할 수 있습니다.

 

리스트의 길이를 n이라고 할 때, k로 나누어 몫(q)과 나머지(r)를 이용할 수 있습니다. q는 나누어져야 할 리스트의 부분이 각각 몇 개의 원소로 이루어져야 하는지에 대한 정보를 담고 있으며, r은 q개씩 묶었을 때 남는 원소의 수입니다. 그렇기 때문에 최종적으로 처음 r 개의 연결 리스트 부분은 q + 1 개의 원소를 갖도록 해야 합니다.

var splitListToParts = function(head, k) {
    const answer = [];
    
    const N = getListLength(head);
    
    // 몫과 나머지 계산
    const q = Math.floor(N / k);
    const r = N % k;
    
    for (let i = 0; i < k; i++) {
        // 첫 r개의 연결리스트는 q+1 크기를 갖도록 설정
        let len = i < r ? q + 1 : q;
        
        // len개의 원소를 읽고, 마지막 원소의 next를 끊어줌
        let cur = head;
        let pre = head;
        for (let j = 0; j < len && cur != null; j++) {
            pre = cur;
            cur = cur.next;
        }
        if (pre != null) { pre.next = null; }
        
        answer.push(head);
        head = cur;
    }
    
    return answer;
}

시간 복잡도를 생각해보면, 구현 상 이중 반복문을 사용하기는 했지만 결국 연결 리스트를 전체적으로 1번 순회한 것이기 때문에 $O(N)$의 시간 복잡도를 갖습니다. 단, $k > N$인 특수한 케이스에는 $O(k)$의 시간 복잡도를 가질 수 있습니다. 하지만, 문제의 제약 조건($0 \le N \le 1000$, $1 \le k \le 50$)을 감안할 때, $N > k$가 더 일반적으로 보이기 때문에 $O(N)$이라 표현하는 게 더 적합해 보입니다.

 

Github: 725.js

GitHub - opwe37/Algorithm-Study