(프로그래머스 c++)예산

https://programmers.co.kr/learn/courses/30/lessons/12982

코딩테스트 연습 - 예산

최대한 많은 부서에 예산을 줘야하기 때문에

주어진 d 배열을 오름차순으로 정렬한다.

 

이후 이진 탐색을 진행.

0 ~ mid 인덱스까지의 예산을 더하여 budget보다 작을 때까지의 front 값을 찾아 리턴하면 된다.

const binarySearch = (d, mid, budget) => {
    let sum = 0;
    
    for(let i = 0; i <= mid; i++){
        sum += d[i];
        
        if(sum > budget){
            return true;
        }
    }
    
    return false;
}

const solution = (d, budget) => {
    let front = 0;
    let back = d.length - 1;
    
    d.sort((a, b) => a - b);
    
    while(front <= back){
        const mid = Math.floor((front + back) / 2);
        
        if(binarySearch(d, mid, budget)){
            back = mid - 1;
        } else{
            front = mid + 1;
        }
    }
    
    return front;
}