[프로그래머스] 예산 (Python)

✏️ 문제

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

코딩테스트 연습 - 예산

✏️ 풀이

그리디 알고리즘의 대표적인 예제로 그 순간에 가장 최적인 것, 즉 작은 것을 고르는 문제이다.

무게 제한이 있는 가방에 가장 여러 개의 물건을 담기 위해서는 무게가 가벼운 것부터 넣는 것이 당연하기 때문!

(최적으로 담으려면 당연히 다른 알고리즘을 써야한다.) 

반복문을 돌면서 최소값을 선택하여 예산에서 빼고, 해당 값은 배열에서 제거한다.

이 때 반복문 탈출 조건은

1. list가 비어있을 때

2. budget이 0일 때

3. budget - 선택된 값 이 음수일때, 즉 예산을 초과할 때

이다.

✏️ 코드

def solution(d, budget):
    result = 0
    while True:
        if len(d) == 0:
            break
        if budget == 0:
            break
        if budget - min(d) < 0:
            break
        budget = budget - min(d)
        d.remove(min(d))
        result = result + 1
    return result

✏️ 다른 사람 풀이

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

내 풀이 방식과 거의 같은 원리이다.
크기 순으로 사용할 것이므로 먼저 sort함수로 정렬하여 차례로 탐색하는 것이 더 적합해보인다.

무한 반복문 탈출조건 대신 

예산에서 선택된 요소를 뺀 후, 예산이 마이너스가 되었으면 탈출한다 + list에 대해 반복문을 돌려, 비어있으면 반복문이 종료됨

이렇게 구현되어있다.

-> sort하여 가장 작은 것부터 차례로 더하면서 합이 budget보다 크면 break해도 될 것 같다. 이러나 저러나 같은 풀이이긴 하지만!

 

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

역시 크기 순으로 사용할 것이므로 먼저 sort함수로 정렬하고
budget이 list요소의 총 합보다 작다면 반복문 돌지 않고 바로 리스트의 길이 반환한다 (어차피 예산 내에 모두 선택가능하므로)
총 합보다 작다면 맨 마지막 것, 즉 제일 큰 것을 pop하고, 다시 budget과 남은 list 요소들의 합 비교함
작은 것부터 선택하는 방식이 아니라 큰 것부터 제거하는 방식이라는 점에서 내 풀이와 다르다

따로 count 변수를 두지 않고 남은 list의 길이를 반환하는 방식으로 구현됨