[python3] 382. Linked List Random Node

풀이 일자: 23.03.10

난이도: [Medium]

분류: [Linked List, Reservoir Sampling, Randomized, Math]

문제 내용

문제의 내용은 한 방향의 linkedList가 주어졌을 때 임의의 노드를 리턴하는데 linkedlist의 모든 노드는 모두 같은 선택될 확률을 가지고 있어야 한다.

 

Follow up: Linked List가 극단적으로 크고 길이를 모르는 경우를 가정해보고 O(1)의 space complexity가 되도록 푸는 문제

 

 

문제 해결 흐름

1. 일단 Follow-up을 무시하고 풀어본다면..

→ class 내부의 constructor에서는 linked-list를 끝까지 읽으면서 arr에 저장해놓고 파이썬 내의 내장함수인 random.choice를 사용하면 쉽게 해결된다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    arr = list();

    def __init__(self, head: Optional[ListNode]):
        self.arr.clear();
        while(head):
            self.arr.append(head);
            head = head.next;

    def getRandom(self) -> int:
        return (random.choice(self.arr)).val

=> arr로 저장해놓고 배열 내의 원소를 아무거나 뽑아주는 random.choice함수를 사용해서 풀이

=> 다시 생각해보니 굳이 배열에 ListNode를 넣을 필요없이 val값만 넣어서 random.choice(self.arr)로 처리해도 가능

Time Complexity: O(N)

생성자함수에서 head를 순회하면서 arr에 값을 넣기 때문에 LinkedList의 길이가 시간 복잡도가 될 것이다.

 

Space Complexity: O(N)

head를 순회하면서 모든 노드를 arr에 넣고 있기 때문에 LinkedList의 길이가 공간 복잡도가 될 것이다.

 

 

2. 1번 조건과 2번 조건을 모두 만족하는 방법에 대해서 생각해보자.

→ 단순히 LinkedList를 순회하면서 길이를 찾고 수학적으로 위치를 뽑아낸다면 동등한 확률로 가능하겠다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.i = 0;
        self.head = head;
        while(head):
            self.i += 1;
            head = head.next;

    def getRandom(self) -> int:
        randint = int(random.randrange(0, self.i));
        node = self.head;
        while(randint > 0):
           node = node.next;
           randint -= 1;
        return node.val;

=> 단순하게 LinkedList의 길이를 카운트해서 수학적으로 뽑아내는 방법(%div의 idea를 사용해도 가능)

Time Complexity: O(N)

생성자함수에서 head를 전체 순회하기에 LinkedList의 길이가 시간 복잡도가 될 것이다.

 

Space Complexity: O(1)

배열과 같은 자료구조를 사용하지 않고 변수만 사용하고 있기에 O(1)의 공간복잡도를 가질 것이다.

 

 

다른 해결 방식

1. Official Solution에서는 Reservoir Sampling이라는 알고리즘을 소개하고 있다.

→ input의 길이를 모르고 한정적인 메모리 환경에서 동등한 확률로 임의의 하나를 선택하는 알고리즘이다.

 

[알고리즘 소개] N개의 sample이 있다고 가정하고 이에 S1,S2, S3, S4, ... SN을 붙이고 앞에서부터 2개의 sample씩 하나의 자리를 위해 서로 싸우고 있다고 가정해보자. 이때 각 단계에서 해당 자리를 차지하고 있는 상태를 X1,X2,...,Xn이라고 한다면, 현재 1/N으로 각각이 동일한 확률로 마지막에 선택되기를 원하는 상황이다. 우선 X1에는 S1이 들어가 있는 상태이고 X2부터는 기존에 있던 S1과 새로운 sample인 S2가 붙게 되어 S1이 이길 확률이 1/2라고 한다면 S3에게도 1/2의 확률로 이기고 ... 마지막까지 가면 1/2^(n-1)의 확률로 하나의 자리를 마지막까지 지키게 될 것이다. 그에 반해 SN의 경우 S1은 도장깨기를 해서 다 올라와야 하는데 1번만 이기면 마지막의 자리는 SN 것이므로 1/2의 확률로 차지하게 될 것이다. => 그렇다면 여기서 불합리해지는 것을 확인할 수 있다. 이를 해결하기 위해 i번째 단계에서 현재 새로들어온 sample을 1/i의 확률로 해당 자리를 차지하게 하고 (1-1/i)의 확률로 이전의 우승자가 해당 자리를 차지하는 것을 유지하게 한다면 모두 같은 선택 확률을 가지게 된다. 이렇게 한다면 임의의 j번째 들어오는 원소가 끝까지 유지되는 확률은 1/j * j/(j+1) * (j+1)/(j+2) *  ... * (N-1)/N = 1/N으로 같아지게 된다.

 

더 자세한 내용을 알고 싶다면 아래의 내용을 참조하는 것이 좋을 것 같다.

Reservoir Sampling Algorithm - 순차적으로 한 번에 하나의 샘플만 볼 수 있고 전체 샘플 개수를 모르는

 

이를 기반으로 짜본다면

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):     
        self.head = head;

    def getRandom(self) -> int:
        scope = 1;
        chosen = 0;              # 현재 선택된 노드의 val
        curr = self.head;

        while curr:
            if random.random() < 1 / scope:       # 1/i의 확률로 현재의 값을 넣고
                chosen = curr.val;                # 안되는 경우 기존의 값을 유지
            curr = curr.next;                     # 다음 sample로 넘어감
            scope += 1;                           # 인덱스 증가
        return chosen;

=> 매우 획기적인 방법으로 충분히 언젠가 써먹을만한 알고리즘인 것 같다.

Time Complexity: O(N)

랜덤을 뽑는 함수에서 head를 전체 순회하기에 LinkedList의 길이가 시간 복잡도가 될 것이다.

 

Space Complexity: O(1)

배열과 같은 자료구조를 사용하지 않고 변수만 사용하고 있기에 O(1)의 공간복잡도를 가질 것이다.

 

 

문제 링크

https://leetcode.com/problems/linked-list-random-node/description/

Linked List Random Node - LeetCode