250212_lah.md

문제 해석

• 최대 몇 개의 부서에 물품을 지원할 수 있는지 return

최종 제출 코드

• 신청 금액이 적을수록 지원가능한 부서가 많아지므로 d를 오름차순 정렬
• 신청 금액이 작은 순서대로 넣어서 최대 횟수를 계산

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

  d.sort((a, b) => a - b);

  for (let cost of d) {
    if (budget >= cost) {
      budget -= cost;
      answer += 1;
    } else {
      break;
    }
  }
  return answer;
}

시간 복잡도

• 정렬 : O(N log N)
• 탐색 : O(N)
• ∴ O(N log N)

메모

• 처음에는 주어진 BUDGET을 딱 맞춰야한다고 잘못 생각해서 DP?로 풀어야하나 했는데 최대 부서 개수를 구하는 문제였으므로 작은 순서대로 정렬 >> 예산 초과하지 않는 범위에서 횟수 계산!
• 정리하자면
  • 최대한 많은 부서를 지원한다 >> 그리디
  • 정확히 BUDGET을 맞춰야한다 >> DP 사용