LeetCode 138(Copy List with Random Pointer, Python)

1. 문제 링크

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

Copy List with Random Pointer - LeetCode

2. 문제 설명

• 연결 리스트가 주어지는데 다음 노드를 가르키는 .next 속성 뿐 아니라 연결 리스트 중 임의의 노드를 가르키는 .random 속성도 가지고 있음.
• 연결 리스트의 head만 주어졌을 때 이와 똑같은 값과 연결 관계를 가진 연결 리스트를 deep copy하여 head를 반환하기.
• 이때, 주어진 연결 리스트의 노드 자체를 참고하면 안된다.

3. 처음 풀이

• 주어진 리스트를 한 번 순회하며 .val, .next 정보를 복사한다.
• 주어진 연결 리스트와 새로 만든 연결 리스트를 처음부터 순회하며, .random 정보를 연결한다.
• 이때, 두 리스트에 cur 를 하나 정해두고 random을 head에서부터 한 칸씩 이동하여 cur.random과 같아질 때 까지 이동한다. 같아지면 새로 만든 연결 리스트에서 cur.random을 연결해주고 cur를 하나 이동 시킨다. 이를 반복. n²의 시간 복잡도.

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
            
        head_copy = Node(head.val)
        cur_copy = head_copy
        cur_origin = head
        cur_origin = cur_origin.next

        while cur_origin: # .val 과 .next를 복사한다. 
            cur_copy.next = Node(cur_origin.val)
            cur_copy = cur_copy.next
            cur_origin = cur_origin.next

        cur_copy = head_copy
        random_copy = head_copy
        cur_origin = head
        random_origin = head 

        while cur_copy: # .random 을 복사하는 과정. cur_copy, cur_origin은 동시에 한 칸씩 이동
            while random_origin != cur_origin.random: # random_origin을 head에서 출발시켜 cur_origin.random 과 같을 때까지 이동
                random_copy = random_copy.next
                random_origin = random_origin.next
            cur_copy.random = random_copy # cur_copy.random 연결
            cur_copy = cur_copy.next # cur_copy 한 칸 이동
            cur_origin = cur_origin.next # cur_origin 한 칸 이동
            random_copy = head_copy # random_copy를 head_copy로 초기화
            random_origin = head # random_origin을 head로 초기화
        
        return head_copy

 

4. 다른 풀이

• 해쉬맵 이용하는 풀이. 처음에 비슷한 시도를 하였으나 dict.get 메소드를 몰라서 key error가 나서 처리하는 도중 풀이 방향을 바꾸었다. dict[key]의 경우 key가 없으면 에러가 나지만 dict.get(key)는 key가 없으면 None 반환.
• 수학에서 isomorphism 함수와 비슷한 느낌이다.
• 시간 복잡도 O(n), 공간 복잡도 O(n)

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        mapping = {}  # 원본 노드와 복사된 노드의 매핑을 저장할 딕셔너리

        # 복사한 노드의 리스트 생성 및 매핑
        cur_origin = head
        while cur_origin:
            mapping[cur_origin] = Node(cur_origin.val)
            cur_origin = cur_origin.next

        # 복사한 노드의 next와 random 포인터 설정
        cur_origin = head
        while cur_origin:
            mapping[cur_origin].next = mapping.get(cur_origin.next)
            mapping[cur_origin].random = mapping.get(cur_origin.random)
            cur_origin = cur_origin.next

        return mapping[head]

---

• Interweaving 기법
• 1→2→3→4 가 주어졌을 때
• 1→1'→2→2'→3→3'→4→4' 로 만들고 .random을 연결한 후
• 1→2→3→4, 1'→2'→3'→4'로 다시 쪼개는 풀이
• 시간 복잡도 O(n), 공간 복잡도 O(1)

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        
        curr = head
        while curr: # 1→2→3→4 가 주어졌을 때 1→1'→2→2'→3→3'→4→4' 로 만드는 과정
            new_node = Node(curr.val, curr.next)
            curr.next = new_node
            curr = new_node.next
            
        curr = head
        while curr: # 1'의 random은 1의 random의 next임. 이를 이용하여 random 연결.
            if curr.random:
                curr.next.random = curr.random.next
            curr = curr.next.next
        
        old_head = head
        new_head = head.next
        curr_old = old_head
        curr_new = new_head
        
        while curr_old: # 섞여있는 old, new를 다시 두칸씩 건너며 풀어주는 작업.
            curr_old.next = curr_old.next.next
            curr_new.next = curr_new.next.next if curr_new.next else None
            curr_old = curr_old.next
            curr_new = curr_new.next
            
        return new_head

 

5. 배운 점

• dict.get(key)는 딕셔너리 key가 없을 경우 None을 반환한다.
• Interweaving 기법이 꽤 강력하고 자주 쓰일 듯하다. 마치 지퍼를 지그재그 짜맞추고 풀어주는 느낌, 바느질을 하는 느낌이다.