[프로그래머스] 예산

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

프로그래머스

문제 설명

1. 예산 안에서 지원해줄 수 있는 부서의 최대수

2. 주의) 예산 남는 금액은 상관없음.

 

코드 설명

1. 예산 남는 금액을 최대로 만들면 많은 부서에 지원가능

    d 오름차순으로 정렬 > 순서대로 예산에서 빼준다 

    예산이 음수가 되면 반복문을 나간다.

import java.util.Arrays;

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

 

재귀버전

 

코드 해석

1. 최대 부서 수(==예산에서 배열 요소를 뺀 횟수) =

                                예산에서 배열 첫번째 요소를 뺀 횟수 + 첫번째 요소를 제외한 나머지 범위에서 뺀 횟수 

2. base case: 1. 예산이 음수가 되면 0을 반환한다. 2. 예산 양수, 배열의 인덱스 idx가 d.length-1되면 1을 반환한다.

import java.util.Arrays;

class Solution {
    static int Re(int budget, int[] d, int idx){
        budget -= d[idx];
        if(budget < 0) return 0;
        else if(idx == d.length-1) return 1;
        else {
            int n = 1 + Re(budget, d, idx+1);
            return n;
        }
    }
    public int solution(int[] d, int budget) {
        Arrays.sort(d);
        return Re(budget, d, 0);
    }
}