[LeetCode] 475. Heaters

😎풀이

1. 이진탐색의 효율 최적화를 위한 houses와 heaters 오름차 순 정렬
2. 정렬된 집 목록 순회
   2-1. 이진 탐색을 통해 가장 가까운 히터의 위치 반환
   2-2. 최적의 히터가 집과 가장 멀리 떨어진 거리라면, 최대 거리 갱신
3. 모든 집을 따뜻하게 유지하기 위해 필요한 최소 거리 반환

function findRadius(houses: number[], heaters: number[]): number {
    const sortedHouses = houses.toSorted((a, b) => a - b)
    const sortedHeaters = heaters.toSorted((a, b) => a - b)
    let maxRadius = -Infinity
    for(const house of sortedHouses) {
        const nearestHeater = findNearestHeater(sortedHeaters, house)
        const radius = Math.abs(house - nearestHeater)
        maxRadius = Math.max(maxRadius, radius)
    }
    return maxRadius
};

function findNearestHeater(heaters: number[], house: number) {
    const heaterLen = heaters.length
    let left = 0
    let right = heaterLen - 1
    while(left <= right) {
        const mid = Math.floor((right + left) / 2)
        if(house === heaters[mid]) return heaters[mid]
        if(house > heaters[mid]) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    const dist1 = right >= 0 ? Math.abs(house - heaters[right]) : Infinity
    const dist2 = left < heaters.length ? Math.abs(house - heaters[left]) : Infinity
    return dist1 <= dist2 ? heaters[right] : heaters[left]
}