level1_예산

 

 

내가 제출한 코드

def solution(d, budget):
	answer = 0
    d.sort()
    for i in d:
    	budget -= i
        if budget < 0:
        	break
        answer += 1
    return answer

 

d를 오름차순으로 정렬해준 뒤 budget에서 빼주는 식으로 코드를 짰다.

또한 budget이 음수가 될 때 빠져나온다.

 

다른사람이 제출한 코드

def solution(d, budget):
	d.sort()
    while budget < sum(d):
    	d.pop()
    return len(d)

 

조건문에서 주어진 budget이 d 리스트에 있는 모든 항목의 합보다 작은 동안 계속 반복되는 구조였다. 

d.pop()는 d 리스트의 마지막항목을 제거하는 함수인데, 리스트가 오름차순으로 정렬되어 있기 때문에 가장 비용이 높은

항목부터 제거하여 예산 안에서 항목들을 맞췄다.

 

여기서 while budget < sum(d) 라인은 sum(d)를 매 반복마다 계산하게 되므로 비효율적일 수도 있다고 한다.

예를 들어서 리스트 d의 길이가 n일 때, sum(d)의 호출은 O(n)의 시간 복잡도를 가지지만,

d에서 원소를 하나씩 제거하는 과정이 많이 반복된다면, 전체 코드의 시간 복잡도 O(n^2)에 이를 수 있다.

 

이를 개선하기 위한 방법 중 하나가 제거되는 항목의 값을 budget에서 빼는 것이라고 한다. 

def solution(d, budget):
    d.sort()
    total_cost = sum(d)  # 미리 전체 비용을 계산
    while d and budget < total_cost:
        total_cost -= d.pop()  # 마지막 원소를 제거하고 그 값을 total_cost에서 뺌
    return len(d)