Programmers / 예산 / Python

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 예산

문제 사이트: https://programmers.co.kr/learn/courses/30/lessons/12982

---

*문제 포인트가 최대로 몇개의 부서를 지원해줄 수 있는가 이기 때문에 여기에 맞추어 문제를 풀어야한다.

 

나의 풀이

def solution(d, budget):
    d.sort()
    cnt = 0
    #예산에서 가장 작은 값들을 빼나가는 구조
    for i in d:
        if i <= budget:
            cnt += 1
            budget -= i
        else:
            break
    return cnt

sort()함수가 오름차순으로 정열해주는 것이지만,

이것도 자료복잡도가 O(NlognN)이기 때문에 알고리즘을 공부해보고 sort함수를 이용하지 않고 구현해보도록 하자

 

다른 풀이

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

sum()이 반복되어 시간 복잡도가 O(n^2)가 되니 매번 원소 값을 하나씩 빼는 편(O(n))이 낫다.

알고리즘을 공부해보니 코드가 짧아도 시간복잡도를 계산해보게되어 점점 다르게 코드를 구현하는 법도 생각해보게 되는 것 같다.

---

※ 알아야 할 것

- 문제의 조건을 제대로 파악해보자. 최대로 지원할 수 있는 부서의 수만 고르면 되므로 그에 맞는 값만 생각하자.

- 시간복잡도를 생각하면서 문제를 풀어보자.