[200424] 이분탐색(Binary Search) - 예산(level3)

1. 문제이해

- budgets의 합이 M이하이면 그대로 배정

- M 초과이면 상한액을 지정해 상한액 이상인 budgets은 상한액으로 처리

 

2. 전략

① budgets를 오름차순으로 배열

② limitIndex 함수 : 합이 M보다 작은 값 중 최대값을 가지는 index 구하기(이진탐색 이용)

- M보다 작음 :

**마지막 원소(모든 요청 가능) --> 해당 mid 출력

그 다음 원소값은 M보다 큼 --> 해당 mid 출력

else limitIndex(budgets, M, mid+1, end)

- M보다 큼 :

**첫 번째 원소(모든 요청 불가) --> -1출력

limitIndex(budgets, M, start, mid-1)

③ answer 구하기

- 모든 요청 가능 : 마지막 원소 출력

- 모든 요청 불가능 : M / 원소개수

- else : mid원소 + (남은 합 배분한 값)

 

3. 참고사항

- 내 방법의 문제점 : 예외처리가 많고 이진탐색으로 원소를 찾은 후 추가계산 필요

- 더 나은 방법 :

이진탐색의 대상을 인덱스가 아닌 budgets값 자체로 한다!!(범위 : 0 ~ budgets[budgets.length-1]);

재귀함수 대신 start <= end일 때까지를 대상으로 한다.(이진탐색의 일반적인 방법)

 

4. 코드

import java.util.*;

class Solution {
    static int sum = 0;
    public int solution(int[] budgets, int M) {
        int answer = 0;
        Arrays.sort(budgets);
        int index = limitIndex(budgets, M, 0, budgets.length-1);
        if(index == budgets.length -1){ //모든 요청 가능
            answer = budgets[index];
        }
        else if(index == -1){ //모든 요청 불가능
            answer = M / (budgets.length);
        }
        else{
            int remain = (M-sum) / (budgets.length-index-1);
            answer = budgets[index] + remain;
        }
        
        return answer;
    }
    
    public int limitIndex(int[] budgets, int M, int start, int end){
        int mid = (start + end) / 2;
        int target = budgets[mid];
        sum = 0;
        for(int i = 0; i < budgets.length; i++){
            if(i <= mid) sum += budgets[i];
            else    sum += target;
        }
        if(sum <= M){ //M보다 작음. 뒤에 있거나 범위 내
            if(mid == budgets.length-1)  return mid; //마지막 원소 - 모든 요청 가능
            else{
                int next = sum + (budgets[mid+1] - target) * (budgets.length-mid-1);
                if(next > M)   return mid;
                else    return limitIndex(budgets, M, mid+1, end); //M보다 큼
            }
        } 
        else{
            if(mid == 0)    return -1; //첫 원소 - 모든 요청 불가능
            else return limitIndex(budgets, M, start, mid-1);
        }    
    }
}

/*
import java.util.*;

class Solution
{
    public int solution(int[] budgets, int M)
    {
        Arrays.sort(budgets);
        int start = 0, end = budgets[budgets.length - 1];
        while(start <= end)
        {
            int sum = 0;
            int mid = (start + end) / 2;
            for(int element : budgets)
                sum = element > mid ? sum + mid : sum + element;
            if(sum > M) end = mid - 1;
            else
                start = mid + 1;
        }
        return end;
    }
}
*/