[프로그래머스][예산] 정렬을 이용한 풀이

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

프로그래머스

문제에 대한 이해:

각 부서에 지원할 수 있는 전체 예산 금액 budget 이 정해져 있다.

정해진 금액 budget과 부서별로 필요한 예산이 담긴 배열 d가 주어질 때, 예산 한도 내에서 지원할 수 있는 최대 부서의 수를 구하라.

 

 

이 문제를 정리하는 이유:

부서별 필요 예산이 담긴 d를 오름차순으로 정렬하기만 하면 매우 쉽게 풀 수 있는 문제를 또 DFS로 풀려고 했다.

지원할 수 있는 부서의 '수'를 구하는 것이다. 필요 예산이 적은 부서부터 정렬하여 합해가면서 budget을 넘는가, 넘지 않는가를 구하기만 하면 된다. 정렬을 이용한 매우 간단한 문제인지라 다음에도 비슷한 문제를 만나면 상기하고자 정리한다.

 

 

문제풀이:

d를 오름차순으로 정렬한다. 변수 tot에 d의 원소들을 더해간다. 변수 cnt에는 더해온 d의 원소의 수를 센다.(이렇게 세지 않고 d의 인덱스를 활용해도 된다.)

budget과 tot가 일치한다면 여태까지 더해온 cnt를 그대로 리턴하고 tot가 budget보다 커지는 순간이 온다면 cnt-1을 리턴한다.

만약 budget이 처음부터 전체 부서를 지원할 만큼 충분하다면 d의 길이를 바로 리턴한다.

 

 

예시코드:

def solution(d, budget):
    n = len(d)
    
    if sum(d) <= budget:
        return n
    
    d.sort()
    tot = 0
    cnt = 0
    for i in d:
        tot += i
        cnt += 1
        if tot == budget:
            return cnt
        if tot > budget:
            return cnt - 1