[프로그래머스] 예산

문제 링크

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

문제 요약

• 주어진 예산 안에서 모든 도시에 최대한 돈을 줄 수 있는 상한선을 구한다

풀이 흐름

• 도시의 비용을 오름차순으로 정렬한 뒤, 도시 인덱스를 기준으로 이진탐색.
  상한액이 budgets[i] 라고 할 때, 주어진 예산 안에서 모든 금액을 처리할 수 있는지 확인하고, 상한액이 budgets[i+1]인 경우에는 모든 금액을 처리할 수 없다면 정답이 되는 상한액은 budgets[i] 이상이며 budgets[i+1] 미만일 것이다.
  일단 budgets[i] 까지는 있는 그대로 처리가 되는거니까
  M - (budgets[0]~budgets[i] 까지의 합) 을 남은 도시의 수 만큼으로 나누면 그 몫이 상한액이 된다.
• 상한액이 budgets[0]보다 작은 경우, budgets[n-1] 이상인 경우도 존재할 수 있으니 예외처리 필요

---

< 이건 풀이 해설 보면서 알게 된 내용 >
int 배열의 수들 중 가장 큰 값은 stream을 이용해서도 구할 수 있다.

import java.util.stream.*;

int[] budgets;
int max = IntStream.of(budgets).max().orElse(0);    // 값이 없으면 0 사용

int 배열의 수들의 총 합을 구하는 것도 stream을 이용하여 구할 수 있다.

// stream을 사용할 때 function 안에서 사용된 변수는 가변 변수를 사용하면 안되니까 final 붙여줌
final int mid = (min + max) / 2;
IntStream.of(budgets)
    .map(b -> Math.min(b, mid))
    .sum();

---

코드

풀이 언어 : JAVA

import java.util.*;

class Solution {
    public boolean isInBudget(int[] budgets, int M, int i, int sum) {
        // i번째 수 까지의 합이 sum
        int n = budgets.length;
        int result = sum + budgets[i]*(n-i-1);
        if(result <= M)
            return true;
        else
            return false;
    }

    public int solution(int[] budgets, int M) {
        int answer = 0;
        int[] budgets_sum = new int[budgets.length];

        Arrays.sort(budgets);

        int sum=0;
        int idx = 0;
        for(int b : budgets) {
            sum += b;
            budgets_sum[idx++] = sum;
        }

        int n = budgets.length;
        int lo = 0, hi = n-1;

        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(isInBudget(budgets, M, mid, budgets_sum[mid])) {
                if(mid+1 < n && !isInBudget(budgets, M, mid+1, budgets_sum[mid+1])) {
                    // 답은 mid와 mid+1 사이에 있음
                    answer = (M - budgets_sum[mid]) / (n - mid - 1);
                    break;
                }else if (mid+1 == n){
                    answer = budgets[n-1];
                    break;
                }else {
                    lo = mid+1;
                }
            }else {
                hi = mid-1;
            }
        }
        if(hi < 0) {
            // 가장 작은 수 보다 적은 상한이 필요하면
            answer = M/n;
        }

        return answer;
    }   
}