Copy List with Random Pointer

💬 문제

[문제 링크]

값 val, 다음 노드를 가리키는 포인터 next, 랜덤 노드를 가리키는 포인터 random
으로 이루어진 _Node를 연결한 리스트의 시작 노드 head가 주어짐
이 리스트를 깊은 복사한 새로운 연결 리스트의 시작 노드 반환

✍️ 나의 풀이

/**
 * // Definition for a _Node.
 * function _Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */

/**
 * @param {_Node} head
 * @return {_Node}
 */
var copyRandomList = function(head) {
    let loop = head;
    let map = new Map();
    
    while (loop) {
        map.set(loop, new Node(loop.val));
        loop = loop.next;
    }

    loop = head;
    while (loop) {
        let newNode = map.get(loop);
        newNode.next = map.get(loop.next) || null;
        newNode.random = map.get(loop.random) || null; 
        loop = loop.next;
    }

    return map.get(head);
};

map을 사용하여 원래 노드 : 새 노드 방식으로 저장
처음에는 값만 복사하여 각 노드를 만들어 놓고
다시 처음부터 순회하여 next와 random에 노드를 할당
원래 노드의 next와 random이 null일 경우 map.get의 결과가 undefined이므로
그럴 경우에는 null을 넣어주도록 해야함
반환 값은 head를 키로 하는 값 노드

📌 결과

Accepted
Runtime 47ms (Beats 90.76%)
Memory 50.96MB (Beats 32.56%)

📚 러닝 포인트

중복 생성 없이 random에 새로운 리스트의 노드를 할당하는 방법이 도저히 생각이 안 나서 결국 솔루션의 힘을 빌렸다. 그 중 map을 사용하는 것이 제일 이해하기 쉽고 획기적인 방법이라 선택했다. 아무래도 map 때문에 메모리 beats가 낮게 나왔지만 그만큼 추가적인 작업이 없어서 런타임 효율이 좋았던 것 같다.