문제 개요
단일 연결 리스트(singly linked list)가 주어졌을 때, 리스트 안에서 임의의 노드 하나의 값을 반환하는 문제입니다. 여기서 중요한 조건은 모든 노드가 동일한 확률로 선택되어야 한다는 점입니다. 예를 들어 리스트가 [1, 2, 3]이라면 반환되는 값은 반드시 1, 2, 3 중 하나여야 하며, 각 값이 선택될 확률은 정확히 1/3이 되어야 합니다.
접근 방법: 저수지 샘플링(Reservoir Sampling)
리스트의 전체 길이를 미리 알 수 없거나 한 번의 순회만 허용되는 상황에서 균등한 확률을 보장하려면 저수지 샘플링 기법이 가장 적합합니다. 핵심 아이디어는 간단합니다. i번째 노드를 방문할 때 1/i의 확률로 그 노드의 값을 결과 변수에 저장하고, 순회가 끝난 후 저장된 값을 반환하는 것입니다. 이 방식은 각 노드가 정확히 1/n(n은 노드 총개수)의 확률로 최종 선택되도록 수학적으로 보장합니다.
알고리즘 단계
getRandom() 메서드에서 다음 작업을 수행합니다.
ret := -1, len := 1, v := head로 초기화합니다.
v가 NULL이 아닌 동안 반복합니다.
rand() % len == 0이면 ret := v의 값으로 갱신합니다.
len을 1 증가시킵니다.
v := v->next로 다음 노드로 이동합니다.
최종적으로 ret을 반환합니다.
C++ 구현 예제
다음 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
class Solution {
public:
ListNode* x;
Solution(ListNode* head) {
srand(time(NULL));
x = head;
}
int getRandom() {
int ret = -1;
int len = 1;
ListNode* v = x;
while(v){
if(rand() % len == 0){
ret = v->val;
}
len++;
v = v->next;
}
return ret;
}
};
main(){
vector<int> v = {1,7,4,9,2,5};
ListNode *head = make_list(v);
Solution ob(head);
cout << (ob.getRandom());
}
입력
[1,7,4,9,2,5]로 리스트 초기화 getRandom()을 호출하여 랜덤 노드 값 획득
출력
4 9 1
출력 결과는 실행할 때마다 달라질 수 있습니다. 생성자에서 난수 생성기(rand())의 시드가 현재 시간(time(NULL))으로 설정되기 때문에, 호출 시점마다 서로 다른 노드 값이 반환됩니다. 위 예제에서는 getRandom()을 세 번 호출한 결과 4, 9, 1이 차례로 출력되었습니다.