[JAVA] 프로그래머스 : 예산 (코딩테스트 고득점 kit > 이분탐색)

https://programmers.co.kr/learn/courses/30/lessons/43237?language=java

코딩테스트 연습 - 예산

이분탐색을 응용하여 문제를 구현하였음

이분탐색 알고리즘 코드

int BinarySearch(int arr[], int target) {
    int start = 0;
    int end = arr.length - 1;
    int mid;

    while(start <= end) {
        mid = (start + end) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

해결 방안 제시에 앞서 이분 탐색을 이용하여 알고리즘을 구현할 때 위와 같은 코드를 이해하고 있으며 이 코드를 응용하여 구현하는 것이 좋음

 

해결 방안

1. 무엇(start, mid, end)을 이분 탐색할 것이고 어떤 걸(위의 BinarySearch 코드의 target) 비교하여 다음 탐색 구간을 정할지 먼저 찾음
=> 이분 탐색할 것: 예산의 상한액(mid) 
=> 비교대상(target) : M(주어진 총 예산)

2. 예산의 최대 상한액(answer)을 구하므로 예산의 상한액(mid)을 이분 탐색함

3. Input에서 비교 대상으로 M(주어진 총 예산)이 주어지므로 M을 target으로 정해 다음 탐색 구간을 정함

4. M과 비교하기위해 상한액을 적용한 budgets 배열들의 합(sum)을 구하는 알고리즘이 포함되어야함

5. answer를 구하기 위해 최대 상한액을 찾아내야함

이분 탐색 알고리즘 코드와 해결 방안을 조합하여 구현하면 아래와 같은 코드가 될 수 있음

 

코드

import java.util.*;
// 예산
class Solution {
    // budgets: 지방에서 요청한 예산 / M: 총 예산
    public int solution(int[] budgets, int M) {
        int answer = 0;
        long sum = 0;
        
        Arrays.sort(budgets);
        
        for(int budget : budgets){
            sum += budget;
        }
        
        // 요청하는 예산들의 합 <= 총 예산
        if(sum <= M){
            // 상한액은 가장 큰 값
            answer = budgets[budgets.length-1];
        }
        // 요청하는 예산들의 합 > 총 예산
        else{
            
            int start, mid, end;
            sum = 0;
            // 예산의 크기
            start = 0; 
            mid = 0;
            end = budgets[budgets.length-1]; 
            
            // 이진 탐색
            while(start <= end){
                
                mid = (start + end) / 2;
                
                sum = 0;    
                // sum 구하기
                for(int i=0; i<budgets.length; i++){
                    if(budgets[i] < mid){
                        sum += budgets[i];
                    }
                    else{
                        sum += mid;
                    }
                }
                
                // 비교대상
                if(sum > M){
                    end = mid - 1;
                }
                else{
                    start = mid + 1;
                    answer = Math.max(answer, mid);
                }
                
            }
        }
        
        return answer;
    }
}