프로그래머스, 자바스크립트) 예산

예산

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

프로그래머스

 

풀이

메모리: 33.7 MB, 시간: 6.48 ms

 

d는 부서별로 신청한 금액이 들어있는 배열, budget은 예산이다. 최종적으로 구해야하는 건 지원할 수 있는 물품의 수.

 

예산이 적은 팀부터 처리하기 위해 금액을 오름차순으로 정렬한다.
각 팀의 요청 금액이 남은 예산을 초과하면 반복을 중단하고 초과하지 않으면 금액을 예산에서 차감하고 결과 값을 증가시킨다.

function solution(d, budget) {
  let result = 0;
  let leftBudget = budget;

  // 비용이 적은 순으로 정렬
  const costSort = [...d].sort((a, b) => a - b);

  for (const cost of costSort) {
    if (leftBudget < cost) break; // 조기 리턴
    leftBudget -= cost;
    result++;
    // console.log(leftBudget, result); 
  }

  return result;
}

 

다른 풀이

메모리: 33.6 MB, 시간: 0.22 ms

 

오름차순 정렬까진 동일하나, 반복문에서 인덱스를 활용한다.

합계가 예산을 넘어가기 전까지의 인덱스가 지원할 수 있는 물품 수가 된다. 

function solution(d, budget) {
  d.sort((a, b) => a - b); // 오름차순 정렬

  let sum = 0;

  for (let i = 0; i < d.length; i++) {
    sum += d[i];
    if (sum > budget) return i; // 초과 시 그 전까지가 정답
  }

  return d.length; // 모두 처리 가능한 경우
}

코드 스타일을 다르게 바꿔보려면 reduce를 사용할 수 있다. (조기 종료는 안됨)

function solution(d, budget) {
  d.sort((a, b) => a - b);
  let sum = 0;
  return d.reduce((count, cost) => {
    sum += cost;
    return sum <= budget ? count + 1 : count;
  }, 0);
}