[프로그래머스] 예산

문제 이해하기

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 계산하는 문제였다. 단 모든 예산을 지원해야 한다.

문제 해결 방법 설명하기

1. 경우의 수 계산하기 

 문제를 풀기 위해서 먼저 경우의 수를 계산해야 하는데 부서별 지원여부를 두고 경우의 수를 계산하면 2(해당 부서의 지원 여부 O or x)^100(부서의 개수)가 나오게 되고, 제한시간안에 문제를 해결할 수 없다. 따라서 완전 탐색은 사용할 수 없게 된다.

 최대한 많은 부서에 예산을 지원하면 되기 때문에 예산 요청이 작은 순으로 지원하면 된다. 따라서 그리디하게 지원하면 문제를 해결할 수 있다. 

코드

def solution(d, budget):
    answer = 0
    d.sort()
    
    for i in range(len(d)):
        if budget - d[i] >= 0:
            budget -= d[i]
            answer += 1
        else:
            break   
        
    return answer




if __name__ == "__main__":
    d = [1, 3, 2, 5, 4]
    budget = 9
    print(solution(d, budget))  # 3

코드 리뷰

다른 사람의 코드인데 상당히 참고할 만 하다. 단점은 sum에서 O(N)의 시간이 걸리지만 문제를 d의 크기가 작으니 상관없다.

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

 

배운점 정리하기

pop과 sum을 이용하면 굉장히 편하다.