[프로그래머스] Lv.1 예산 (greedy, 탐욕, 그리디 알고리즘, Java)

▶ 그리디 알고리즘 활용한 간단한 문제가 있어 정리해보고자 합니다.

 

문제설명

입력 & 출력

나의 풀이

import java.util.*;

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

 

각 부서에서 요청한 예산이 들어있는 배열 d와 예산의 총합 budget이 주어졌을 때, 최대 몇 개의 부서에 예산을 배정할 수 있는지를 구하는 문제입니다.

 

이번 문제는 는 그리디 알고리즘을 활용하면 간단히 풀 수 있습니다.

 

문제에서 그리디 알고리즘을 활용할 수 있는 이유는 다음과 같습니다.

 

❗❗주의❗❗
배열이 오름차순으로 정렬이 되어있어야 합니다

 

1. 오름차순 정렬 : 부서들의 예산 요청을 오름차순으로 정렬해야 합니다.
2. 적은 값부터 예산 배정: 오름차순으로 정렬했기 때문에 정렬된 배열의 첫 번째 요소부터 예산을 배정합니다. 이는 가장 적은 예산부터 차례대로 배정하는 것입니다.
3. 최대한 많은 부서에 배정: 예산이 적은 부서부터 배정을 했기에 최대한 많은 부서에 예산을 배정할 수 있습니다.

 

위와 같은 방법 때문에 그리디 알고리즘은 최적의 해를 보장합니다.

 

간단히 얘기하면 "적은 금액부터 예산을 배정해 나가므로 최대한 많은 부서에 예산을 나누어줄 수 있기 때문입니다."

 

풀이설명을 하자면 Arrays.sort() 메서드를 사용하여 배열을 오름차순으로 정렬합니다.

 

그리고 예산 요청 배열인 d만큼 순회를 하는데 0번째 요소부터 sum변수에 누적을 하면서 요소를 증가시킵니다.

 

합계를 누적했을 때 예산 budget보다 작으면 예산배정을 했다는 의미이기 때문에 answer을 증가시킵니다.

 

예산을 넘어간다면 break문을 통해 반복문을 그 즉시 빠져나옵니다.

 

참고 ❗

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기