[프로그래머스/java] 예산 (Summer/Winter Coding 2018)

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

코딩테스트 연습 - 예산

 

• 문제의 핵심!
          꼭 예산을 0만큼 남기라는 것이 아니라 나눌 수 있는 최대 부서면 된다는 것
          그렇다면 작은 금액부터 나누어주는 방식이면 최대로 나누어줄 수 있겠지!
          그래서 정렬부터 해주고 시작한다.
  
  

 

import java.util.*;

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        
        int sum = 0;
        
        /* 문제의 핵심!
        꼭 예산을 0만큼 남기라는 것이 아니라 나눌 수 있는 최대 부서면 된다는 것
        그렇다면 작은 금액부터 나누어주는 방식이면 최대로 나누어줄 수 있겠지!
        그래서 정렬부터 해주고 시작한다.
        */
        
        Arrays.sort(d);
        
        for(int i = 0; i < d.length; i++) {
            if(sum + d[i] > budget) { // 예산 초과되면 그만
                break;
            }
            
            sum += d[i];
            answer++;
        }
        
        return answer;
    }
}