이번에 풀어볼 문제는
https://school.programmers.co.kr/learn/courses/30/lessons/12982
문제로 아주 간단한 탐욕법 알고리즘 문제다.

문제 설명

주요 키워드

주요 키워드를 살펴 보자면 전체 예산이 정해져 있기 때문 과 최대한 많은 부서에서 탐욕법, 그리디 알고리즘을 사용해야 한다는 것을 알 수 있다.

입출력 예시

입출력 예시에서 보면 친절하게도 [1,2,3], [1,2,5], [1,3,4] 처럼 정렬된 예시를 미리 보여줬다.

그럼 이제 그리디 알고리즘과 정렬을 해야 한다는 것을 알게되었으니 코드를 보도록 하겠다.

코드

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        Arrays.sort(d); // 신청 금액을 오름차순 정렬
        int count = 0; // 지원 가능한 부서 수
        
        for (int cost : d) { // 작은 금액부터 예산에서 차감
            if (budget >= cost) { 
                budget -= cost;
                count++;
            } else {
                break; // 예산 부족하면 종료
            }
        }
        
        return count;
    }
}

이진 탐색을 할 경우 조금 더 빠를 수 있겠지만 적은 규모의 데이터로는 충분히 괜찮은 성능의 코드라고 생각된다.