[1스4코2파] # 197 LeetCode 138. Copy List with Random Pointer

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (197차)
[4코1파] 2023.01.13~ (189일차)
[1스4코1파] 2023.04.12~ (100일차)
[1스4코2파] 2023.05.03 ~ (78일차)

Today :

2023.07.19 [197일차]
Binary search
138. Copy List with Random Pointer

981. Time Based Key-Value Store

https://leetcode.com/problems/time-based-key-value-store/description/

문제 설명

link list가 주어질 때, 각 노드에는 next 포인터와 random 포인터가 있다. random 포인터는 해당 리스트내부의 무작위 노드를 가리키는데 이 링크드리스트를 복사하여 새로운 링크드 리스트를 만드는 것

문제 풀이 방법

노드의 값을 복사하는 것은 깊은 복사로 하는데,
random 노드를 기존 리스트와, 새 리스트에 해당하는 노드포인터와, 순서를 해시테이블에 저장하고. 이를 이용해 새로운 리스트의 각 노드의 ramdom포인터를 구해야 한다.

두 개의 해시테이블의 key, value순서가 서로 다르기 때문에, 저장된 해시테이블에서 순서에 따른 노드를 바로 얻는다.
원본리스트와 새 리스트의 같은순서의 노드를 서로 mapping 시켜 놓는 식으로 구현한다.

내 코드

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]':
        oldToCopy = {None:None }

        cur = head
        while cur:
            copy = Node(cur.val)
            oldToCopy[cur] = copy
            cur = cur.next

        cur = head
        while cur:
            copy= oldToCopy[cur]
            copy.next = oldToCopy[cur.next]
            copy.random = oldToCopy[cur.random]
            cur = cur.next

        return oldToCopy[head]

증빙

여담

링크드리스트 싫은데.. 쪼렙은 링크드리스크밖에 안남았네...