[알고리즘] 예산

문제 파악

주어진 예산 안에서 최대로 지원할 수 있는 부서의 수를 구하라.

접근 방법

정해진 예산 안에서 최대한 많은 부서에 지원을 해야한다.

그렇다면 부서별 요청 금액이 들어 있는 배열을 오름차순으로 정렬해준다.

그 후 예산 범위 보다 작거나 같을 때까지 앞에서 부터 차례대로 더한 후 더한 횟수를 반환하면 된다.

코드 구현

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        int sum = 0;
        
        Arrays.sort(d); // 주어진 배열을 오름차순 정렬
        
        // 배열을 하나씩 꺼내서 더한다.
        // 더한 값이 budget보다 커지면 반복문을 종료한다.
        // 문제에서는 budget보다 작거나 같은 경우를 원하기 때문에 더한 횟수에서 1을 뺀다.
        // budget보다 커진 경우는 한 번을 더 더했기 때문이다.
        for(int i = 0; i < d.length; i++) {
            sum += d[i];
            answer++;
            
            if(sum > budget) {
                answer--;
                break;
            }
        }
        
        return answer;
    }
}

배우게 된 점

Arrays.sort() 메소드를 배웠습니다.

해당 메소드를 배우기 전에는 코드록 정렬을 직접 구현해서 사용했었는데, Arrays.sort()를 알게 된 뒤 코드가 훨씬 간결해져서 좋았습니다.