프로그래머스 예산

어려웠던 점

1. 언제까지 반복해야 하나 ->log_2(max - min)+1 번

2. 예산 상한액을 어떻게 측정하나 -> 가능한 상한액을 list에 넣고 최대값 출력

3. 테스트 케이스 9번, 런타임 에러 -> n개의 도시에 예산을 배분할 때 (M // len(budgets)가 min(budgets)를 넘지 못하면 (M // len(budgets)가 최대 예산이다.

 

마지막 테스트 케이스는 유효한지 모르겠다. 세 도시에 1씩 나눠줄 수 없어서 1,1,0 이렇게 나눠야 하는데 균등하게 분배한다고 하면 0이 맞는 것 같다.

 

도시 예산의 총 합이 M 이하면 도시 예산 중 최대값 반환

전체 예산을 각 도시에 균등하게 분배할 수 있는 금액이 최소 도시 예산도 넘지 못하면 균등하게 분배할 수 있는 금액 반환

이분탐색으로 최소, 평균, 최대를 갱신하면서 예산 계산 시 M을 넘지 않는 상한액을 list에 저장후 반복이 끝나면 최대 avg 반환

from math import log


def solution(budgets, M):
    if sum(budgets) <= M:
        return max(budgets)
    mn = min(budgets)
    distributable_budget = M // len(budgets)
    if mn >= distributable_budget:  # 전체 예산 중 각 도시에 분배할 금액이 도시의 최소 예산도 넘지 못하면
        return distributable_budget  # 전체 예산을 도시 수로 나눈 금액이 분배할 수 있는 최대 예산이나 마찬가지다.
    mx = max(budgets)
    avg_list = []
    i = 0
    lg2 = log(mx-mn, 2)
    while i < lg2:
        budget_tmp = []
        avg = (mx + mn) // 2
        for n in budgets:
            if avg >= n:
                budget_tmp.append(n)
            else:
                budget_tmp.append(avg)
        if sum(budget_tmp) > M:
            mx = avg
        elif sum(budget_tmp) <= M:
            avg_list.append(avg)
            mn = avg
        i += 1
    return max(avg_list)


print(solution([120, 110, 140, 150], 485))
print(solution([9, 8, 5, 6, 7], 5))
print(solution([1, 2, 3], 3))
print(solution([1, 1, 1], 3))
print(solution([1, 1, 4], 3))
print(solution([2, 3, 4], 2))

 

출처 https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산 | 프로그래머스