문제 설명
국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.
제한 사항
지방의 수는 3 이상 100,000 이하인 자연수입니다.
각 지방에서 요청하는 예산은 1 이상 100,000 이하인 자연수입니다.
총 예산은 지방의 수 이상 1,000,000,000 이하인 자연수입니다.
입출력 예
입출력 예
✍내 코드
import java.util.*;
class Solution {
public int solution(int[] budgets, int M) {
int answer = 0;
int max = 0;
// 정렬
Arrays.sort(budgets);
for(int budget : budgets){
max = Math.max(max, budget);
}
answer = binarySearch(budgets, 0, max, M);
return answer;
}
private int binarySearch(int[] budgets, int min, int max, int total) {
int start = min;
int end = max;
while (start <= end) {
long sum = 0;
int mid = (start + end) / 2;
for (int budget : budgets) {
if (budget >= mid) {
sum += mid;
} else {
sum += budget;
}
}
if (sum < total) {
start = mid + 1;
} else if (sum > total){
end = mid - 1;
} else {
return mid;
}
}
return end;
}
}
import java.util.stream.*;
class Solution {
public int solution(int[] budgets, int M) {
int min = 0;
int max = IntStream.of(budgets).max().orElse(0);
int answer = 0;
while(min <= max) {
final int mid = (min + max) / 2;
int sum = IntStream.of(budgets)
.map(b -> Math.min(b, mid))
.sum();
if(sum <= M) {
min = mid + 1;
answer = mid;
} else {
max = mid - 1;
}
}
return answer;
}
}