[Java] [Algorithm] Budget

1 minute read

Problem description

In order to support the goods needed by each department, Company A examined how much each department needed to buy goods. However, we cannot provide products to all departments because the total budget is fixed. Therefore, I want to make things available to the maximum number of departments.

When buying things, each department must apply and support the entire amount. For example, a department that applied for 1,000 yen should always support 1,000 yen, and less than 1,000 cannot be supported.

If array d and budget containing the applied amount for each department are given as parameters, create a solution method so that it will return the maximum number of departments that the thing can support.

Condition

  • d is an array containing the amount of money applied for by department, and the length (total number of departments) is 1 or more and 100 or less. -Example) If d.length = 2, the number of departments is 2. -Example) If d[0] = 3, the application amount for department 1 is 3.
  • The value of d is the amount applied for each department. The application amount is a natural number between 1 and 100,000.
  • budget is a budget. The budget is a natural number between 1 and 10,000,000.

I/O example

| d | budget | result | |:—————–|——————:|:——— ———:| | [1,3,2,5,4] | 9 | 3 | | [2,2,3,3] | 10 | 4 |

Commentary

*The explanation is a code I created, so if you have a better algorithm, please share it!


import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        
        Arrays.sort(d); // ascending sort
        
        int cnt = 0; // For counter of department that can support
        for (; cnt <d.length; cnt++) {
            budget -= d[cnt]; // Every time we support, we reduce from budget
            
            if (budget <0) break;
        }
        
        return cnt;
    }
}