[프로그래머스] 예산

1.  문제 설명

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

2. 제한사항

• d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
• d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
• budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.

3. 입출력예

d	budget	result
[1,3,2,5,4]	9	3
[2,2,3,3]	10	4

4. 풀이(과정 or 최종)

Solution 1 ( 덧셈 )

import java.util.Arrays;
class Solution {
    public int solution(int[] d, int budget) {
        Arrays.sort(d);
        int answer = 0;
        int useBudget=0;
        for(int i=0; i<d.length; i++){
            useBudget += d[i];
            if(useBudget > budget) break;
            answer++;
        }
        return answer;
    }
}

Solution 2 ( 뺄셈 )

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

5. 풀이 설명

1. 예산을 적게 신청한 부서들을 먼저 더하는게 제일 많은 부서에게 예산을 줄 수 있는 방법이다.

   1-1. 부서에서 신청한 예산을 적은 순서대로 정렬해준다.

2-1. 적은 예산을 신청한 부서부터 더하여 주어진 예산보다 많지 않으면 answer를 늘려준다.

2-2. 주어진 예산에서 적은 예산을 빼서 주어진 예산이 0보다 작지 않으면 answer를 늘려준다.

6. 결과 

Solution 1 ( 덧셈 )

Solution 2 ( 뺄셈 )

7. 마치며

어려운 문제는 아니었다.

덧셈부터 떠올랐는데 뺄셈도 할 수 있다는걸 인식시켜줄 필요는 있었다.!