프로그래머스 | 예산 [파이썬 python]

프로그래머스

 

코드

def solution(d, budget):
    answer = 0 # 가능한 부서의 수
    for i in sorted(d):
        budget -= i
        if budget < 0: 
            break
        answer += 1
    return answer

부서별로 신청한 금액이 들어있는 배열 d가 있을 때, 주어진 예산 budget으로 최대 몇 개의 부서에 지원할 수 있는지 구하는 문제이다.

최대한 혼자 풀어보기 위해 고민하고 고민했지만 어려웠다.

처음에는 조합(combinations)을 사용했지만 d의 길이가 최대 100이기 때문에 모든 조합을 구하는 과정에서 시간초과가 발생했다.

결국 어떻게 해결해야 할지 모르겠어서 다른 사람들의 질문들을 참고해 해결하였다.

 

이 문제는 문제 자체를 이해하는 것이 제일 중요하다.

문제 설명과 주어진 테스트 케이스에 대한 풀이를 보면 budget을 모두 사용해야 하는 것처럼 느껴진다.

하지만, 이 문제는 budget을 모두 사용하는 것이 아니라 budget으로 지원할 수 있는 최대 부서의 개수(=배열 d 요소의 개수)를 구하는 문제이다.

쉽게 말해, budget은 남아도 된다는 것이다.

 

그럼 어떻게 하면 주어진 budget으로 최대한 많은 부서에 지원할 수 있을까?

작은 금액을 요구하는 부서들을 우선으로 처리하면 한정된 budget으로 많은 부서에 지원할 수 있다.

그러므로 주어진 배열 d를 오름차순으로 정렬하여 적은 금액부터 budget으로 가능한지 판단한다.

 

budget에서 부서의 요구 금액 i를 뺀다.

i만큼 차감하고 남은 budget이 0보다 크면 해당 부서는 지원이 가능하므로 answer+1을 해준다.

계속해서 순서대로 부서의 요구 금액을 차감한다.

만약, 차감한 budget이 0보다 작으면 해당 부서는 지원할 수 없는 것이다.

더 이상 budget으로 지원이 불가능하므로 반복문을 break 하고 지금까지 지원한 부서의 개수를 return 한다.