[프로그래머스 / 파이썬 풀이] 예산

첫 시도 코드 (실패)

def solution(d, budget):
    answer = 0
    visited = [0] * len(d)
    result = []
    
    def dfs(sum_n, index, cnt):
        if sum_n > budget:
            return
        
        if index >= len(d):
            return result.append(cnt)
        
        if visited[index] == 0:
            visited[index] = 1
            dfs(sum_n + d[index], index+1, cnt+1)
            visited[index] = 0
            dfs(sum_n, index+1, cnt)

        
    dfs(0, 0, 0)
    answer = max(result)
    return answer

첫 시도는 dfs를 통해 모든 경우의 수를 생각하고 풀이했는데 시간초과가 났다.

 

시간초과의 해결 방법을 생각해보면 예산 배열을 sort 하고 sort 한 값을 전체 예산에서 적은 요구 예산부터 빼준다면 그 값이 최대 일 것이다.

 

두 번째 시도 코드 (실패. 런타임에러)

def solution(d, budget):
    answer = 0
    d.sort()

    i = 0
    while budget > 0:
        if budget - d[i] < 0:
            break
        budget -= d[i]
        i+=1
        answer+=1
    
    return answer

런타임에러가 발생한 코드. 생각해보면 요구 예산 전체를 더했을 때 예산보다 적은 경우 처리를 해주지 않았다. 그로인해 i가 계속 증가하면서 list에 포함되지 않는 index를 검색 해서 런타임 에러가 생겼다.

 

세 번째 시도 코드 (성공)

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

두 번째에서 놓친 부분의 코드를 추가하면서 성공.