#프로그래머스_예산 - Java 자바

#유형 : 이분탐색

#난이도 : LV3

#이분탐색의 기본적인 문제로써, 주어진 배열을 정렬하여 오름차순으로 만들어 주는 아이디어까지 생각했다면 다 풀었다고 생각해도 된다. 이후에는 정석적인 이분탐색으로 코딩하여 해결하면 됨

import java.util.*;
class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        
        Arrays.sort(budgets);
        
        long sum = 0;
        for(int i=0; i<budgets.length; i++){
            sum += budgets[i];
        }
        if(sum < M)
            return budgets[budgets.length-1];
        
        int min = M / budgets.length;
        int max = budgets[budgets.length-1];
        int middle = 0;
        int stand = 0; 
        while(true){
            middle = (min+max)/2;
            sum = 0;
            
            for(int i=0; i<budgets.length; i++){
                if(budgets[i] > middle)
                    sum += middle;
                else
                    sum += budgets[i];
            }
            if(stand == middle)
            {
                answer = middle;
                break;
            }
            if(sum > M){
                max = middle;
            }else{
                min = middle;
            }
            stand = middle;
        }
        return answer;
    }
 
}