[프로그래머스] 예산

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

코딩테스트 연습 - 예산

 

 

< 문제 설명 >

그림과 같은 입력이 주어진다.

d는 각 부서에서 신청한 금액이고, budget은 예산이다.

예산안에서 금액을 줄수있는 부서의 최대 개수를 리턴하라.

금액보다 덜 줄 수는 없다.

 

 

< 문제 이해 >

처음에는 combinations를 사용해서 풀면 되겠다고 생각했으나

시간초과가 나왔다. 그래서 조금 더 단순하게 풀 수 있는 방법을 생각해보았는데,

금액을 정렬해서 앞에서부터 더해가면서 예산을 넘지않는 최대 개수를 구하는 방법을 생각했다.

 

 

< 문제 풀이 >

먼저 배열 d를 정렬하고, 0부터 i 까지의 합을 구해 budget보다 클 때까지 for문을 돌리는 것으로 구현했다.

def solution(d, budget):
    d.sort()

    for i in range(len(d)):
        if sum(d[0:i+1]) <= budget:
            continue
        else:
            return i

    return len(d)

 

 

< 풀이 개선 >

다른 코드들을 보니까 내가 sum()을 사용해서 시간이 훨씬 오래 걸린다는 것을 깨달았다.

sum()보다는 하나씩 더하는 방식을 사용했다.

이렇게 푸니까 시간이 훨씬 단축됐다.

def solution(d, budget):    
    d.sort()
    
    tot = 0
    for i in range(len(d)):
        tot += d[i]
        if tot > budget:
            return i
        
    return len(d)