[프로그래머스]예산

[82] 예산

책 구매하기

문제 정보

• 분류: 그리디
• 정답률: 74%
• 권장 시간 복잡도: O(N log N)
• 핵심 키워드: 정렬, 예산 배분, 작은 것부터, 누적합
• 문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12982

문제를 읽을 때 체크할 포인트

더 많은 부서를 지원하려면 비용이 작은 요청부터 처리하는 게 최선이다. 정렬 후 예산이 허용하는 만큼 앞에서부터 더하면 된다.

한 번의 선택 기준이 맞는지만 확인되면 그 뒤는 같은 규칙을 반복하면 된다. 결국 매 순간 무엇을 먼저 선택해야 전체가 가장 이득인지 보는 문제다.

풀이 흐름

1. 부서 요청 금액을 오름차순 정렬한다.
2. 누적합을 더하며 budget을 넘는지 본다.
3. 넘기 직전까지의 개수를 반환한다.

구현할 때 놓치기 쉬운 부분

작은 요청부터 예산에 담아야 더 많은 부서를 지원할 수 있다. 정렬 없이 주어진 순서대로 처리하면 최적해를 보장할 수 없다.

파이썬 정답 코드

def solution(d, budget):
  # 부서 요청 금액을 오름차순 정렬한다.
  answer = 0
  total = 0

  # 누적합을 더하며 budget을 넘는지 본다.
  for cost in sorted(d):
    # 넘기 직전까지의 개수를 반환한다.
    total += cost
    if total > budget:
      break
    answer += 1

  return answer

시간 복잡도

N은 d의 길이이다.

핵심 비용은 정렬이다. N개 데이터를 정렬하는 데 O(N log N)이 들고, 정렬 뒤에 붙는 한 번의 순회나 해시 조회는 선형이라 전체 차수를 바꾸지 않는다.

따라서 시간 복잡도는 O(N log N)이다.