1. 내 코드
# 각 부서가 신청한 금액만큼을 모두 지원
# 최대 몇 개의 부서
def solution(d, budget):
total = 0
# 적은 금액부터 차례로 더해서 budget 이 커버 가능한 최대 개수 return
for i, req in enumerate(sorted(d)):
total += req
# total 이 budget 을 넘을 경우
if total > budget:
return i
# total 이 budget 보다 작을 경우
return len(d)
sort 를 써서 복잡도는 배열길의 n 의 O(nlogn) 이 된다.
일차 반복문 -- O(n)
합 및 비교 연산 -- O(1)
=> 최종 복잡도는 O(nlogn) 이 된다.
2. 다른 사람 풀이
def solution(d, budget):
d.sort()
while budget < sum(d):
d.pop()
return len(d)
이 코드는 프로그래머스에서 좋아요 제일 많이 받은 코드.
sum() 자체는 복잡도가 O(n) 이지만,
while 문이 돌 때마다 매번 다른 값을 sum 해야 해서 복잡도가 O(n²) 이 된다.
그래도 d 에서 하나씩 뺀 다음 길이만 반환하는 로직이 흥미로움.
def solution(d, budget):
d.sort()
cnt = 0
for i in d :
budget -= i
if budget < 0 :
break
cnt += 1
return cnt
budget 에서 아이템을 하나씩 빼는 방식으로 풀이한 코드.
enumerate 썼으면 cnt 변수 선언할 필요 없이 더 깔끔하게 코드 나올 듯.
나처럼 계산 내역을 변수에 다 담아두지 않아도 되고!
