예산

문제

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다. 물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다.

 

예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

 

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

제한사항 

· d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1이상 100 이하입니다. 

· d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다. 

· budget은 예산을 나타내며, 1 이상 10,000,000이하의 자연수입니다. 

 

입출력 예 

d	budget	result
[1,3,2,5,4]	9	3
[2,2,3,3]	10	4

---

풀이

1. Me

def solution(d, budget):
    sum_calc = 0; i = 0
    if sum(d) < budget:
        return len(d)
    else:
        while sum_calc < budget:
            sum_calc += sorted(d)[i]
            if sum_calc > budget:
                return i 
            i += 1 
        return i

문제에서 요구하는 것은 최대한 많은 부서에 지원을 해 주는 것이다. 최대한 많은 부서에 지원을 해 주기 위해서는 신청 금액이 적은 순으로 정렬하고, 합계가 예산보다 커질 때 까지 앞에서부터 차례대로 신청 금액을 더해나가면서 부서 수를 카운트한다.

 

2. Others

def solution(d, budget):
    d.sort()
    while budget < sum(d):
        d.pop()
    return len(d)

다른 사람들의 말에 의하면 효율성 측면(신청한 부서가 많고, 예산이 적은 경우)에서는 문제가 있다고 한다. 신청금액을 정렬하고, 예산이 신청금액의 합계(sum)보다 클 동안(while), 신청금액이 큰 순으로 하나씩 제거.. 

def solution(d, budget):
    d.sort()
    answer = 0 
 
    for i in d :
        budget -= i
        if budget < 0 :
               break
        answer += 1
    return answer

신청금액 리스트를 정렬하고, 예산에서 적은 신청금액 부터 차례로 빼 가며 예산이 0 보다 작아지면 종료하도록 구현하였다.