[프로그래머스 Lv.1] 예산

풀이 날짜 : 2025.04.25
문제 유형 : 연습 문제
문제 제목 : 예산
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12982

Intuition

• 정해진 예산에서 부서에서 신청한 금액을 지원해줄 때, 최대 몇 개 부서에 지원해줄 수 있는지 구해야 한다.
• 신청한 금액이 작은 부서들부터 지원해야 최대한 많은 부서에 지원할 수 있다.
• 현재 상황에서 가장 최적인 선택을 반복해서 전체 최적해를 구하는 그리디 알고리즘 문제로도 볼 수 있겠다.

Approach

• 부서의 신청 금액이 담긴 배열 d를 오름차순으로 정렬한다.
• 오름차순으로 정렬된 d를 순회하며, 부서의 신청 금액(amount)이 남은 예산(budget) 보다 작으면 지원한 부서 수(count)를 1 늘린다.
• count를 반환한다.

Complexity

• Time complexity : O(n log n)
  • d의 길이를 n이라고 할 때 정렬에 O(n log n), d를 순회하는데 O(n)으로, 결과적으로 O(n log n)이다.
• Splace complexity : O(1)
  • 입력값을 제외하면 추가 사용 공간이 거의 없다.

Code (JS)

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

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

    d.forEach((amount) => {
        if (budget - amount >= 0) {
            budget -= amount;
            count += 1;
        }
    })

    return count;
}