예산

문제정의

---

d는 지원을 바라는 부서들의 예산들이고 총 예산은 budget이다. 최대한 지원해 줄 수 있는 부서가 몇 개인지 반환하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

import java.util.*;

public class Budget {
    
    //프로그래머스 문제풀이 level1 예산
    public static void main(String[] args)
    {
        int[] d = {1,3,2,5,4};
        int budget = 9;
        int answer = 0;
        Arrays.sort(d);
        for(int money : d)
        {
            budget -= money;
            if(budget < 0)
                break;
            answer++;
        }
        System.out.print(answer);
    }
}

최대한 많은 부서에게 예산을 지원해주기 위해선 예산 청구가 적은 부서부터 나누어주면 된다. 이를 위해 예산 목록을 오름차순으로 정렬하고 예산이 감당할 수 있는 만큼 돈을 뺀다. 이 문제에서 청구 예산의 일부를 주는 것은 아니었으므로 난이도가 쉬웠다.

시간복잡도는 모든 부서에게 예산을 나눠줄 수 있을 때 d의 크기를 n이라 하면 \(O(n)\)이다.

테스트