이 문제를 풀기 전 이분탐색이 무엇인지 대충은 기억나는데 어떤 자료 형태로 생성해야하는지를 몰라 검색해보았다. 덕분에 데이터 베이스, 알고리즘 수업을 들으면서 배웠던게 제대로 기억이 났다. 이분탐색 문제라서 이분탐색을 사용해서 풀어보려고 다른 알고리즘은 세워보지 않았는데, 문제를 풀고나서 다른 사람 풀이를 보니 이분탐색이 아닌 완전 다른 알고리즘으로 푼 코드가 있었다. 엄청 신박하기도하고 쉽게 생각할 수 없는 알고리즘이었는데 정말 대단하다는 생각이 들었다. 그래서 해당 알고리즘을 참고한 코드도 함께 게시글에 올리니, 다른 분들도 참고해서 보시길! (▰˘◡˘▰)
1. 문제
국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다.
국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다.
그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.
1
2
3
| 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다.
상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다.
|
예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때,
상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다.
각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때,
위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.
제한조건
- 지방의 수는 3 이상 100,000 이하인 자연수입니다.
- 각 지방에서 요청하는 예산은 1 이상 100,000 이하인 자연수입니다.
- 총 예산은 지방의 수 이상 1,000,000,000 이하인 자연수입니다.
2. 알고리즘! 생각해보자
is_ceiling() 함수는 solution에서 매개변수로 받은 budgets, M 변수와 배정한 상한액을 인수로 주고 해당 상한액을 총 예산 M으로 해결 가능하면 true, 못하면 false를 반환하는 함수로, 해당 함수를 먼저 정의해준다.- 제한조건이 각 지방에서 요청하는 예산이 1 이상 100,000 이하이기 때문에 시작값
left를 1, 끝 값 right를 100,000으로 초기화하여 생성한다. - 이분탐색을 위해
left와 right의 중간값을 mid 변수에 초기화하여 생성한다. - 문제의 총 예산 배정 방법 1번에 의해 모든 요청이 배정될 수 있는 경우에
요청한 금액(budgets의 최댓값) 그대로 반환해야하기 때문에 max 변수를 생성해 최댓값으로 초기화 한다. left가 right보다 작은 동안 다음을 반복해 이분탐색을 진행한다.- 상한액
mid를 총 예산 M으로 해결 가능하고, mid가 max 이상이면 max를 반환, max미만이면 mid+1을 총 예산 M으로 해결 가능한지 확인한다. mid+1을 총 예산 M으로 해결 가능하면 상한액이 더 커질수 있다는 뜻이므로 left를 mid로 재할당하고, 가능하지 않으면 mid가 최대 상한액이라는 의미이므로 mid를 반환한다.- 6번의 상한액
mid를 총 예산 M으로 해결할 수 없으면 상한액을 더 낮춰야 하므로 right를 mid로 재할당한다. - 반복문 내에서 값들이 반환되지만, 반복문이 끝나면 마지막에 0을 반환해주고 끝낸다.
3. 해결코드
[C++]
내가 푼 알고리즘 코드 (통과 O)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <algorithm>
#include <vector>
using namespace std;
bool is_ceiling(vector<int> budgets, int M, int ceiling) {
int total = 0;
for(int budget : budgets) {
if(budget > ceiling) total += ceiling;
else total += budget;
}
return total > M? false : true;
}
int solution(vector<int> budgets, int M) {
int left = 1, right = 100000;
int mid = right / 2;
int max = *max_element(budgets.begin(), budgets.end());
while(left < right) {
if(is_ceiling(budgets, M, mid)) {
if(mid >= max) return max;
if(!is_ceiling(budgets, M, mid+1)) return mid;
left = mid;
} else right = mid;
mid = (left + right) / 2;
}
return 0;
}
|
다른 사람 알고리즘 참고한 코드 (통과 O)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <algorithm>
#include <vector>
using namespace std;
int solution(vector<int> budgets, int M) {
int numbers = budgets.size();
sort(budgets.begin(),budgets.end());
for(int budget : budgets){
if(budget > (M / numbers)) return M/numbers;
else{
M -= budget;
numbers--;
}
}
return budgets.back();
}
|
4. 해결능력UP, 깊이 생각해보기
5. 참고해서 문제해결 ٩( ᐛ )و
1
| 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
|
