데일리 알고리즘 230116

데일리 알고리즘 230116

---

프로그래머스, 예산

프로그래머스

 

 

📄 나의 코드

def solution(d, budget):
    d.sort()
    for i in range(1, len(d)+1):
        if(d[0] > budget): # 정렬 후, 첫번째 원소(min(d))가 budget보다 큰 경우, 예외처리
            return 0
        if(sum(d[:i]) > budget):
            break
        else:
            answer = i
    return answer

print("d : [1,3,2,5,4], budget : 9, reault : ", solution([1,3,2,5,4], 9))
print("d : [2,2,3,3], budget : 10, reault : ", solution([2,2,3,3], 10))
print("d : [3,1,1], budget : 3, reault : ", solution([3,1,1], 3))
print("d : [7,5,6], budget : 2, reault : ", solution([7,5,6], 2))

---

처음엔 조합문제로 이해하고 조합 구할 수 있는 라이브러리로 접근해 문제를 풀었다.

 

📄 나의코드-조합 라이브러리 이용

def solution(d, budget):
    if(min(d)>budget):
        return 0
    from itertools import combinations
    for r in range(1, len(d)+1):
        for c in combinations(d, r):
            if(sum(c) > budget):
                break
            else:
                answer = r
    return answer

 

📌 런타임 에러

from itertools import combinations
for c in combinations(d, r):

이 부분이 압도적으로 시간을 잡아먹음.

 

d에서 r만큼 원소를 뽑아 모든 경우의 수를 순회.

d의 원소의 갯수를 n이라고 할때

n! / (r! * (n-r)!)

순회하는 횟수는 위와 같다.

 

만약, 원소의 갯수(n)이 100개이고 r이 5라고 하면,

100 * 99 * 98* 97*96 / 5*4*3*2*1 = 75,287,520를 순회함.

따라서 combination을 쓰지 않고 푸는 방법을 생각해봐야 한다.