[Java] 예산 Lv1

예산

문제 프로그래머스 FAQ 내용을 보니 카카오나 기업의 문제들은 저작권이 있으니 풀이를
github나 개인블로그에 올리지 말라고 되어 있어서 링크로 대체합니다.

출처: Programmers
예산

문제의 이해

-내가 이해한 문제의 조건 어떤 복잡한 내용이 있는지 알았는데 간단했다. 주어진 예산 내에서 최대한 많은 부서를 지원하면 된다. 내가 생각한 문제 해결방법은 오름차순으로 숫자를 정렬 후 앞에서부터 쭉 더해나가다가 그 수가 주어진 budget을 넘어가면 끝. 그때 구해진 부서의 수가 최대로 지원 할 수 있는 부서의 수이다. 이유는 정해진 값 내에서 제일 많은 부서를 지원 할 수 있는 방법은 작은 숫자들은 최대한 많이 더하는 것이다.

내가 생각한 풀이 방법

1. 주어진 부서별 요청금액의 배열인 d를 오름차순으로 정렬한다.
2. 정렬된 배열의 요소를 처음부터 순서대로 더한다.
3. 더할 때마다 answer++를 해주어 지원부서의 수를 계산한다.
4. 더한 값이 주어진 최대예산 budget을 넘어서면 현재까지 answer값이 최대로 지워할 수 있는 부서의 수이다.

풀이

첫 번째 풀이

풀이방법 그대로 풀었다. (사실 조금 쉽다고 느껴져서 그냥 코드부터 작성하고 풀이방법을 씀)

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        int temp = 0;
        
        //이거 하나 못만듬... (구글 검색으로 결국 완성은 했는데.. 선택, 삽입, 버블 정렬 3개 중 하나는 최소한 완벽!!!! 하게 구현할 수 있도록 하자)
        for(int i = 0; i < d.length - 1; i++){
            for(int j = 1; j < d.length - i; j++){
                if(d[j - 1] > d[j]){
                    temp = d[j - 1];
                    d[j - 1] = d[j];
                    d[j] = temp;
                }
            }
        }
        temp = 0;
        for(int i = 0; i < d.length; i++){
            temp += d[i];
            if(temp > budget){
                break;
            }   
            answer++;
        }
        return answer;
    }
}