[Programmers] L1. 예산 (Python)

---

[문제 링크] 👇

프로그래머스

---

풀이

1️⃣ 정렬

• 리스트를 오름차순으로 정렬한다.
• 예산 내에서 최대한 많은 요청을 지원하려면, 작은 금액부터 순서대로 처리하는 것이 유리하다.
• 작은 요청을 먼저 처리해 예산을 조금씩 소진해 나가면 더 많은 항목을 충족할 수 있다.

 

2️⃣ 예산 차감 및 지원 항목 증가

• 정렬된 금액들을 하나씩 순회하며 budget에서 차감한다.
• budget이 0보다 작아지는 순간, 현재 예산으로는 이 요청을 처리할 수 없도록 한다. 이때 루프를 종료한다.
• 만약 budget이 0보다 작아지지 않으면, 지원 가능한 항목의 수(answer)를 1 증가시킨다.

 

Solution

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

 

코드 개선점

한 가지 주의할 점은, 예산을 초과하는 경우의 조건을 다음과 같이 개선할 수 있다.

for i in d:
    if budget - i < 0:
        break
    budget -= i
    answer += 1

 

이렇게 하면, 예산 초과 시 다시 budget에 더하는 과정 없이 바로 break로 종료된다.

 

 

👩‍💻 회고

시간 초과 코드

from itertools import combinations

def solution(d, budget):
    answer = 0
    for i in range(1, len(d) + 1):
        for j in combinations(d, i):
            if sum(j) <= budget: #예산 이하 것만 확인
                answer = max(len(j), answer)
    return answer

• 이 코드에서 시간 초과가 발생하는 이유는 모든 가능한 부서 조합을 계산하기 때문이다.
• for i in range(1, len(d) + 1): 이 부분에서 모든 조합의 길이를 하나씩 늘려가며 확인한다.
• combinations(d, i)는 d의 요소에서 i개를 뽑아 가능한 모든 조합을 만드는데, 각 길이에 대해 조합 개수는 매우 커질 수 있다.
  • 예를 들어, 리스트의 길이가 n일 때 조합은 2^n 개에 가까워지며, 각 조합에 대해 합을 구하므로 복잡도가 크게 증가한다.

---