문제 링크

프로그래머스 문제

풀이

이분탐색을 통해서 문제를 해결했다.
처음에는 이분탐색이 아닌 완전탐색을 이용해서 문제를 해결하려고 했으나, 너무나 큰 크기로 인해서 실패했다.
하지만 여러 테스트 케이스를 넣으면서 규칙성을 발견하게 되었다.
그건 적당한 수를 찾아서 times를 나눈값들이 n이 되는지 확인하는 것이다.
하지만 이 역시 너무나 큰 경우의 수를 가지고 있었기 때문에
이분탐색으로 풀게 되었다.

이분탐색을 사용하기 위해서는 다음과 같은 조건이 필요해 보인다.
1. 하나의 축내부에 답이 있는지 없는지 확실히 판독이 가능하다 <- 이게 가장 중요함
2. 막대한 범위

코드

function solution(n, times) {
    times.sort((a,b) => a -b)
    var answer = Infinity;
    
    let left = 0;
    let right = n * times[times.length-1]
    let mid = 0;
    let count
    while(left <= right){
        mid = Math.floor((right+left)/2)
        count = 0;
        for(let i=0; i<times.length; i++){
            count += Math.floor(mid / times[i])
            
            if(count >= n){
                answer = Math.min(answer,mid)
                break;
            }
        }
        if(count >= n){
            right = mid -1
        }else if(count < n){
            left = mid +1
        }
    }
    return answer;
}