[LeetCode] 528. Random Pick with Weight

😎풀이

1. w를 순회하며, 각 누적합의 범위와 총합 계산
2. 0 ~ 총합 - 1의 범위에서 랜덤한 정수 뽑기
3. 이진 탐색을 통해 해당 정수가 포함된 범위 인덱스 찾기
4. 해당 인덱스 반환

class Solution {
    private prefixSum: number[]
    private total: number
    constructor(w: number[]) {
        this.prefixSum = []
        this.total = 0
        for(const weight of w) {
            this.total += weight
            this.prefixSum.push(this.total)
        }
    }

    pickIndex(): number {
        const randNum = Math.floor(Math.random() * this.total)
        let left = 0
        let right = this.prefixSum.length - 1
        while(left < right) {
            const mid = Math.floor((left + right) / 2)
            if(randNum < this.prefixSum[mid]) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}