코딩테스트 연습> Summer/Winter Coding(~2018)> 예산

 

<문제링크: https://programmers.co.kr/learn/courses/30/lessons/12982>

코딩테스트 연습 - 예산

 

문제설명: d배열로 주어지는 예산들 중 합산했을 때 budget 범위를 넘지 않는

최대의 예산 개수를 알아내는 문제이다. 최대한 많은 종류의 예산을 선택해야하므로,

오름차순으로 정렬한 후 앞의 숫자부터 차례대로 보면서 budget이 넘지 않을 때까지

count를 해주면 될 것 같다.

 

[1차 시도]

import heapq

def solution(d, budget):
    cnt = 0 
    heapq.heapify(d)
    while d:
        if budget - d[0] >=0:
            budget-= heapq.heappop(d)
            cnt+=1
        else:
            return cnt
    return cnt

 

풀이: heapq라는 파이썬 내장 모듈을 활용해서 문제를 풀어봤다. heapq.heapify를 사용하면 리스트를 heap으로 변환함으로써 최소값을 맨 앞의 숫자로 옮길 수 있다. 이때 시간복잡도는 O(N) 으로 O(N*logN) 인 sort 함수를 사용할 때보다 시간을 줄일 수 있다.

 

heapq.heapify의 과정을 살펴보면,

배열이 d = [3,1,2,5,4] 로 주어졌을 때 heapq.heapify(d)를 한 번 실행하면,

 

d = [1,3,2,5,4] 로 가장 최소값이 맨 앞에 위치하게 되고 원래 있던 숫자와 자리를 바꾼다. 

 

따라서 맨 처음에 한번 정렬을 해주고 while문을 돌린다. 돌면서 만약 d의 0번째 인덱스, 즉 예산 중 최소값을 budget에서 뺀 값이 0이상이라면, 해당 부서는 예산 지원이 가능하므로 budget에서 예산만큼 빼준다. 이때 heapq.heappop을 써서 heap에서 가장 작은 원소를 pop해주고 그 다음 작음 원소를 맨 앞으로 빼준다. 그리고 cnt에 예산 지원 부서를 추가해준다.

 

그리고 만약 예산의 합이 budget을 넘어가면, 즉 현재 예산을 budget에서 뺀 값이 음수라면, 바로 cnt를 return 해주고 d 배열 내 모든 예산이 budget에 맞게 지원가능하다면, while문 종료 후 cnt를 return 한다.

 

 

채첨결과: 테스트케이스 23개 모두 잘 통과한다. 

 

 

 

 

'쫄보의삽질' 블로그 탄생스토리가 궁금하다면:

Git push 취소 방법 (feat. '쫄보의삽질' 블로그 탄생 배경)