[프로그래머스](python) 예산 - Summer/Winter Coding(~2018)

문제

---

🧩 수도 코드 (틀린 풀이)

for문 안에서 d로 len(d)-idx개를 조합한 리스트를 차례로 만들어 개수를 구하고
제일 큰 개수 return

---

🧩 틀린 풀이

def solution(d, budget):
    from itertools import combinations
    combi_lists = []
    answer = 0
    for idx, i in enumerate(d):
        combi_list = list(combinations(d,len(d)-idx))
        for j in combi_list:
            if sum(j) <= budget:
                combi_lists.append(len(j))
                
    return max(combi_lists)

테스트 케이스는 성공했지만
정확성 21.7.. 이런 법은 없는겨...

찾아보니 combinations가 압도적으로 시간을 잡아먹어, 복잡도가 아주 높은 코드가 됐다
시간초과 떠서 확인사살 당한 기분...

---

🏁 내 풀이

def solution(d, budget):
    d.sort()
    answer = 0
    for i in range(len((d)):
        if sum(d[:i+1]) <= budget:
            answer += 1
    return answer 

📌

• d를 정렬하여 1부터 연산할 수 있게
• d[:i] 부터 하면, 0부터 i까지(i 미포함)이므로 i+1로 해줌 (마지막 d까지 연산할 수 있게)
• sum(1), sum(1,2), sum(1,2,3) 까지 answer에 더해져 3이 됨

예산이 적게 드는 부서부터 지원하여 최대로 지원할 수 있는 부서 수를 return

---

🧩 다른 풀이

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

📌

• budget < sum(d)가 True일 동안만 루프
• d.pop()해서 뒤에 제일 큰 숫자들 차례로 pop
• budget < sum(d)가 False가 되면 루프를 나와 return len(d)

---