프로그래머스 예산

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12982

프로그래머스

접근

 

앞서 풀었던 조합 문제와 거의 같다. 

주어진 부서별 예산 n 개의 합이 주어진 예산 m 을 넘지 않을 때까지 합한다.

만약 sum >= m 이면 해당 재귀 종료 준비를 한다.

 

풀이

접근1. 재귀

결과: 틀렸습니다! 재귀로 풀었는데 계속 다른 두 케이스가 같은 답이 나왔다.

 

접근2: 그냥 단순하게 접근하기로. 반복문

결과: 틀렸습니다! 답은 맞게 나오는데 테스트 케이스 몇 개에서 걸렸다.

  const N = d.length;
  let answer = 0;
  let sum = 0;

  for (let i = 0; i < N; i++) {
    sum += sortedD[i];
    if (sum > budget) {
      answer = i;
      break;
    }
  }
  if (sum <= budget) answer = d.length;

  return answer;

접근3: sort 추가

결과: 맞았습니다!

  const sortedD = d.sort((a, b) => a - b);
  const N = d.length;
  let answer = 0;
  let sum = 0;

  for (let i = 0; i < N; i++) {
    sum += sortedD[i];
    if (sum > budget) {
      answer = i;
      break;
    }
  }
  if (sum <= budget) answer = d.length;

  return answer;

function solution(d, budget) {
    d.sort((a, b) => a - b);

    while (d.reduce((a, b) => (a + b), 0) > budget) d.pop();

    return d.length;
}