이분탐색

왜 이분탐색을 할까? 빠르게 원하는 답을 찾기 위해서!

 

[ 풀이법 ]

 

정렬하고 탐색 시작하기!! 

1. 최소 & 최대값의 중간값을 구한다.

2. 조건에 맞춰 총합이 M보다 작으면 최소값이 중간값이 된다.

3. 그렇지 않은 경우, 최댓값이 mid가 된다.

 

-> 종료조건 : 이전의 mid의 값(preMid)가 새로운 mid값과 같으면 탐색을 멈춘다. (모든 값들 탐색 완료)

 

[ 효율성 2번 에러 문제 ]

 

1. 요청한 금액의 총합이 준비된 예산(M)보다 적을 경우, 요청된 예산요청 중 가장 큰 요청을 return

2. 요청한 금액의 총합이 Integer 최대 값을 넘길 수 있으니, Long으로 선언 (효율성 2번 통과 방법)

 

 

static int solution(int[] budgets, int M) {

		int answer = 0;
		int left = 0;
		int right;
		int mid = 0;

		Arrays.sort(budgets);
		right = budgets[budgets.length-1];

		while(left <= right) {
			long sum = 0;
			mid = (left+right)/2;

			for(int budget : budgets) {
				if(budget >= mid) sum += mid;
				else sum += budget;
			}

			if(sum > M) right = mid-1;
			else {
				answer = mid;
				left = mid+1;
			}
		}

		return answer;
	}