LeetCode [528]: Random Pick with Weight

 

📌 LeetCode [528]: Random Pick with Weight

🔗 https://leetcode.com/problems/random-pick-with-weight/

---

문제 설명 📄

0부터 시작하는 양의 정수 배열 w가 주어집니다.
각 w[i]는 i번째 인덱스의 가중치를 나타냅니다.
pickIndex() 함수는 각 인덱스를 가중치에 비례한 확률로 무작위 선택하여 반환해야 합니다.

---

문제 접근 방식

1. w의 전체 합을 계산하여 각 가중치를 비율로 구합니다.
2. 각 가중치를 누적 합 형태로 저장하여 확률 구간을 만듭니다.
3. 무작위로 생성된 값이 해당 구간에 속하는 인덱스를 반환합니다.
4. 효율성을 높이기 위해 이분 탐색을 사용하여 인덱스를 찾는 방식으로 리팩토링할 수 있습니다.

---

Solution 💻

import random
from typing import List

class Solution:

    def __init__(self, w: List[int]):
        self.prefix_sum = []
        current_sum = 0
        total_sum = sum(w)
        
        for weight in w:
            current_sum += weight / total_sum * 100
            self.prefix_sum.append(current_sum)

    def pickIndex(self) -> int:
        target = random.uniform(0, self.prefix_sum[-1])
        for i, val in enumerate(self.prefix_sum):
            if target < val:
                return i

시간 복잡도 분석 ⏲️

• 초기화: O(n)
  • w 배열을 순회하며 누적 합을 계산합니다.
• pickIndex: O(n)
  • prefix_sum 배열을 순차적으로 탐색합니다.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • 누적 합 배열을 저장합니다.

---

리팩토링 🛠️

import random
from typing import List

class Solution:

    def __init__(self, w: List[int]):
        self.prefix_sum = []
        current_sum = 0
        
        for weight in w:
            current_sum += weight
            self.prefix_sum.append(current_sum)

    def pickIndex(self) -> int:
        target = random.uniform(0, self.prefix_sum[-1])
        low, high = 0, len(self.prefix_sum) - 1
        while low < high:
            mid = (low + high) // 2
            if target > self.prefix_sum[mid]:
                low = mid + 1
            else:
                high = mid
        return low

시간 복잡도 분석 ⏲️

• 초기화: O(n)
  • w 배열을 순회하며 누적 합을 계산합니다.
• pickIndex: O(log n)
  • 이분 탐색을 사용하여 인덱스를 찾습니다.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • 누적 합 배열을 저장합니다.