[Programmers/JAVA] 03. 예산

※  예산

https://school.programmers.co.kr/learn/courses/30/lessons/12982

 

 

문제 분석

부서별 신청 금액이 들어있는 배열 d 와 예산 budget 이 주어질 때, 최대 지원 가능한 부서의 수를 구하는 문제이다.

단, 물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 주어야 한다.

 

접근 방법

신청 금액이 작을수록 보다 많은 부서의 물품을 지원해 줄 수 있을 것이므로  정렬  을 이용할 것이다.

 

부서의 개수가 $N$개 일 경우, 정렬의 시간 복잡도는 $O(NlogN)$이고 예산 분배의 시간 복잡도는 $O(N)$이다.

따라서, 평균 시간 복잡도는 $O(NlogN + N) == O(NlogN)$이다.

 

코드 설계

# 지원 가능한 부서의 개수를 저장할 변수 result 를 선언하고 배열 d 를 정렬한다.

# for 문을 돌며 i 값이 증가할 때 마다 budget 값을 d[i] 만큼 감소시키고 budget 값이 0보다 작으면 반복문을 멈춘다.

# budget 값이 0보다 크다면 result 값을 1 증가시키고 다시 반복문을 수행한다.

# result 를 반환한다.

 

코드 구현

import java.util.*;

class Solution {
    public int solution(int[] d, int budget) {
        int result = 0;
        Arrays.sort(d);
        
        for(int i=0; i<d.length; i++) {
            budget = budget - d[i];
            
            if(budget < 0) {
                break;
            }
            
            result++;
        }
        
        return result;
    }
}