[LeetCode] 497. Random Point in Non-overlapping Rectangles

😎풀이

1. 초기화 시점
   1-1. rects를 활용하여 각 사각형의 내의 좌표 개수를 통한 누적값 기록
2. pick 호출 시점
   2-1. 어떤 사각형을 선택할지 기록된 사각형 목록에서 랜덤 선택
   2-2. 사각형 좌표 내의 어떤 좌표를 선택할지 랜덤 선택
   2-3. 선택된 좌표 반환

class Solution {
    private rects: number[][]
    private prefixSum: number[]
    constructor(rects: number[][]) {
        this.rects = rects
        this.prefixSum = []
        for(const [x1, y1, x2, y2] of rects) {
            const xPoints = x2 - x1 + 1
            const yPoints = y2 - y1 + 1
            const rectPoints = xPoints * yPoints
            const lastPrefix = this.prefixSum[this.prefixSum.length - 1] ?? 0
            this.prefixSum.push(lastPrefix + rectPoints)
        }
    }

    pick(): number[] {
        const lastPrefix = this.prefixSum[this.prefixSum.length - 1]
        const target = Math.floor(Math.random() * lastPrefix)
        let left = 0
        let right = this.prefixSum.length
        while(left < right) {
            const mid = left + Math.floor((right - left) / 2)
            if(target >= this.prefixSum[mid]) {
                left = mid + 1
            } else {
                right = mid
            }
        }
        const [x1, y1, x2, y2] = this.rects[left]
        const xRange = x2 - x1 + 1
        const yRange = y2 - y1 + 1
        const randomX = x1 + Math.floor(Math.random() * xRange)
        const randomY = y1 + Math.floor(Math.random() * yRange)
        return [randomX, randomY]
    }
}