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

문제 설명

회사에서 여러 부서가 지원을 요청하며, 총 예산을 초과하지 않는 범위에서 최대한 많은 부서의 요청을 승인하려고 합니다.
각 부서의 지원 요청 금액이 담긴 배열 d와 총 예산 budget이 주어질 때, 예산 내에서 지원할 수 있는 최대 부서의 수를 구하는 문제입니다.

---

제한 조건

1. d의 길이: 1 이상 100 이하
2. 각 부서의 지원 요청 금액: 1 이상 100,000 이하
3. 총 예산 budget: 1 이상 10,000,000 이하

---

해결 방법

알고리즘: 그리디 (Greedy)

1. 문제의 핵심
   • 예산을 최대한 많은 부서에 나누어주려면, 작은 금액부터 순차적으로 처리해야 합니다.
   • 이를 위해, 부서 요청 금액을 오름차순 정렬합니다.
2. 구현 방식
   • 배열 d를 오름차순으로 정렬합니다.
   • 요청 금액을 하나씩 누적하여 합산합니다.
   • 합이 총 예산 budget을 초과하면, 그 시점까지 승인된 부서의 개수를 반환합니다.
3. 예산 초과 시 처리
   • 요청 금액을 합산하는 과정에서 예산을 초과하면, 더 이상 부서를 승인할 수 없으므로 즉시 종료합니다.
4. 모든 요청이 예산 내에 포함되는 경우
   • 반복문이 끝날 때까지 예산을 초과하지 않으면, 모든 부서가 승인됩니다.

---

시간 복잡도

1. 정렬 연산
   • d를 정렬하는 데 O(n log n).
2. 합산 연산
   • 최대 n번 순회하므로 O(n).
3. 총 시간 복잡도
   • O(n log n).

---

구현 코드

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;
}