예산(프로그래머스, Java)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산 | 프로그래머스

알고리즘 설명

빠르게 예산에 맞는 상한 값을 찾아내는 것이 핵심이다. - 이분탐색

• 주어진 budgets 배열의 값들 중에서 가장 큰 값을 end라 주고 start는 나올 수 있는 가장 작은 값 0을 주고 시작

• start와 end의 중간 값이 상한 값이라고 기관들의 요구 예산(budgets 배열의 값들)들을 변환하여 계산해본다.

• 주어진 예산(M)값 보다 같거나 작다면상한 값이 될 수 있고 answer에 값을 넣어준다 물론 이분탐색을 더 진행한다면 더 높은 상한 값을 찾을 수 있다.

• 이분탐색은 탐색범위의 중간 값을 내가 찾는 값이라고 생각하는 탐색 방법이다.

막혔던 지점:

중간 값이 아닌 평균 값으로 상한 값을 찾으려고 했다. 시간도 오래걸리고 정확한 값이 안나오는 경우도 존재하였다.

유명한 알고리즘에는 이유가 있다...

 

package test;

public class Budget {
	public static int solution(int[] budgets, int M) {
		int size = budgets.length;
		int start=0;

		int end = 0;
		for(int i= 0; i<size;i++) {
			if(end<budgets[i])end=budgets[i];
		}
		int mid = 0;
		int sum = 0;
		int answer = 0;
		
		while(start<=end) {
			sum = 0;
			mid = (end+start)/2;
			for(int var : budgets) {
				if(var<mid)
					sum+=var;
				else
					sum+=mid;
			}

			if(sum>M) {
				end = mid-1;
			}else {
				answer = mid;
				start = mid+1;
				
			}
			
		}
		return answer;

	}

	public static void main(String[] args) {
		int M = 485;
		int budgets[] = { 120, 110, 140, 150 };

		System.out.println(solution(budgets, M));

	}

}