1️⃣서론
프로그래머스 level3 문제 예산입니다.
Javascript를 이용하여 해결하였습니다.
2️⃣문제 설명
3️⃣풀이
이 문제는 이분탐색을 활용하는 문제입니다. 예산을 0부터 M까지 잡고 이분탐색을 하며 가능한 예산을 탐색하여 답을 도출하는 문제입니다. 그럼 문제를 보고 가겠습니다.
4️⃣ 내가 푼 소스코드
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
32
33
34
35
36
37
38
39
40
const solution = (budgets, M) => {
let answer = 0;
const sum = budgets.reduce((acc, cur) => {
return acc + cur;
}, 0);
//모든 예산이 배정될수 있는경우 가장 큰 값을 리턴하면 답이된다.
if (sum <= M) {
let max = 0;
for (let i = 0; i < budgets.length; i++) {
if (budgets[i] > max) {
max = budgets[i];
}
}
return max;
} else {
let min = 0;
let max = M;
//이분탐색을 하며 합이 예산과 일치하거나 똑같은 값이 두번 나오는 순간 답을 리턴한다.
while (true) {
let num = Math.floor((max + min) / 2);
if (answer === num) return answer;
const calculateBudget = budgets.reduce((acc, cur) => {
if (cur > num) {
return acc + num;
} else {
return acc + cur;
}
}, 0);
if (calculateBudget === M) return num;
else if (calculateBudget < M) {
min = num;
answer = num;
} else {
max = num;
answer = num;
}
}
}
};
5️⃣ 결론
이분탐색을 활용하는 문제를 처음 풀어봤는데 탐색을 하기전에 정렬을 하여 테스트 케이스 2번에서 자꾸 시간초과가 났습니다. 이 이분탐색은 예산을 이분탐색하는 것이라 굳이 정렬을 할 필요가 없다는 것을 깨달았습니다. 이 문제점 때문에 좀 시간이 오래걸렸던 것 같습니다. 좀더 노력해야 겠습니다. 감사합니다.
6️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
