🎯1주차A "예산"
문제 설명
백준 2512번(실버3)
국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.
- 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
- 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다.
여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.
제한사항
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.
첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.
입출력 예
| 입력 | 출력 |
|---|---|
| 4 120 110 140 150 485 | 127 |
| 5 70 80 30 40 100 450 | 100 |
✔️정렬된 예산액들에서 최대, 최소를 구하고 이분탐색을 이용하여 최대 == 최소가 될 때까지 조건을 반복한다.
✍내 코드
import java.util.*;
class Solution {
public int solution(int[] budgets, int M) {
int answer = 0;
Arrays.sort(budgets);
int limit = M / budgets.length;
if(limit == 0) return answer = 0;
int low = 0;
int mid = 0;
int high = budgets.length;
while(low <= high) {
mid = (low + high) / 2;
if(budgets[mid] > limit) {
high = mid - 1;
}
else if(budgets[mid] == limit){
break;
}
else {
low = mid + 1;
}
}
for(int i=0; i<=mid; i++) {
if(mid == 0) break;
M -= budgets[i];
}
int left = budgets.length - (mid+1); // 배정해야 할 남은 예산 개수
if(left == 0) {
answer = M;
}
else {
answer = M / left;
}
return answer;
}
}
✏️효율성은 커녕 정확성에서도 5점밖에 얻지 못한 완전히 틀린 코드이다..ㅠㅠ (+런타임 에러)
아직 저 코드를 수정하지 못했지만 틀린 이유를 찾아보았다.
- 런타임 에러가 났던 이유는
int high = budgets.length부분에서 index 범위를 초과했기 때문이다. - 답이 틀린 이유 중 하나는 남은 예산이 배정되어야 할 최대값보다 클 때 상한액을 최대값으로 return해줘야 하는데 하지 않았다.
- 하지만 여전히 4%에서 틀린 답이라고 나온다. (다시 에러 찾으러 가야지.. ㅠ)
강의내용
✔️이분탐색을 이용하기 위해 최소=0, 최대를 구한다.
✔️중간값 mid를 구하고 상한액으로 가정한 뒤, 예산들을 돌면서 mid값보다 작으면 해당 예산값을, mid값보다 크면 mid값을 더한 총 합(sum)을 구한다.
✔️sum이 국가 예산보다 작거나 같으면 최소값을mid+1로, 크면 최대값을mid-1로 다시 설정하여 sum값을 구한다.
💡 Tip. 좋은 프로그램을 만드는 방법
1. 당면한 문제를 해결한다.
2. 좋은 코드가 되도록 계속 리팩토링 한다.
✍🏻정답 코드
public int solution(int[] budgets, int M) {
int answer = 0;
int min = 0;
int max = 0; // 이분탐색을 위해 최소, 최대 예산값을 찾는다.
for(int b : budgets) {
if(b > max) max = b;
}
while(min <= max) {
final int mid = (min + max) / 2;
int sum = 0;
for(int b : budgets) {
if(b > mid) sum += mid;
else sum += b;
}
if(sum <= M) {
min = mid + 1;
answer = mid;
}
else {
max = mid -1;
}
}
return answer;
}✍🏻정답 코드 - 리팩토링
public int solution(int[] budgets, int M) {
int answer = 0;
int min = 0;
// 이분탐색을 위해 최소, 최대 예산값을 찾는다.
// 스트림을 이용하여 구할 수 있다.
// 리턴값으로 Optional(int)가 나오는데 값이 있을수도, 없을수도 있다는 의미. => 값이 없을 때는 0 (.orElse(0))
int max = IntStream.of(budgets).max().orElse(0);
while(min <= max) {
final int mid = (min + max) / 2;
int sum = 0;
//스트림을 이용하여 sum값을 더 쉽게 구할 수 있다.
sum = IntStream.of(budgets)
.map(b -> Math.min(b, mid)) // 스트림을 사용할 때 람다식 안에 사용되는 값은 가변변수를 사용하면 안된다. final로 바꿔주기
.sum();
if(sum <= M) {
min = mid + 1;
answer = mid;
}
else {
max = mid -1;
}
}
return answer;
}