.leetcode(138. Copy List with Random Pointer)

https://leetcode.com/problems/copy-list-with-random-pointer/

 

1. 2022/05/07 시도

소요시간: 21분( 공간복잡도 O(n)), 13분( 공간복잡도O(1))

// 공간복잡도 O(n)
class Solution {
    public Node copyRandomList(Node head) {
        
        Map<Node, Node> map = new HashMap<>();
        Node dummyNode = new Node(0);
        Node dummyHead = dummyNode;
        Node current = head;
        while (current != null) {
            Node newNode = new Node(current.val);
            dummyNode.next = newNode;
            newNode.random = current.random;
            map.put (current, newNode);
            
            dummyNode = dummyNode.next;
            current = current.next;
        }
        
        dummyNode = dummyHead.next;
        while (dummyNode != null) {
            if (dummyNode.random != null) {
                dummyNode.random = map.get(dummyNode.random);
            }
            
            dummyNode = dummyNode.next;
        }
        
        return dummyHead.next;
    }
}

// 공간복잡도O(1)
class Solution {
    public Node copyRandomList(Node head) {
        Node current = head;
        while (current != null) {
            Node newNode = new Node(current.val);
            newNode.next = current.next;
            current.next = newNode;

            current = current.next.next;
        }
        
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }

            current = current.next.next;
        }
        
        current = head;
        Node prev = new Node(0);
        Node prevHead = prev;
        while (current != null) {
            prev.next = current.next;
            current.next = current.next.next;
            prev = prev.next;
            current = current.next;
        }
    
        
        return prevHead.next;
    }
}

풀이 접근 과정

공간복잡도 O(n)
- 이거는 map을 이용해서 기존 노드와 대응되는 노드를 저장하고
- 순회하면서 기존 노드로 저장되어있는 random필드를 신규 노드로 대체한다.

공간복잡도 O(1)
- 이거는 만들때부터 기존과 신규를 노드로 이어버린다.
- 그다음에 두번째 돌때는 random을 신규 노드로 매칭하는 코드를 작성한다.
- 마지막으로 기존과 신규 노드를 분리한다.

 

느낀점

• 맨 처음에는 random노드를 가지고 swap해서 데이터를 바꿔치기 하려고 했따. 이 방법은 여러 random노드가 한 노드를 가르킬 때, 소용이 없다. 이렇게 노드끼리 이어붙이고 분리해내는 풀이는 획기적이다.
• 나 역시 힌트를 보고서 이 방법의 접근방버을 캐치했다. 다음에는 처음부터 풀어보고 싶다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형