[프로그래머스/Javascript] 예산

알고리즘

Posted by Kyun2da on July 20, 2020

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️⃣ 마치며..

질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️