[프로그래머스 코딩테스트 연습] 예산 (Python3) Lv1

https://school.programmers.co.kr/learn/courses/30/lessons/12982

프로그래머스

 

 

정답 코드

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

 

 

문제 해결 과정

1. 배열 정렬: d.sort()

먼저, 부서별 신청 금액 배열 d를 오름차순으로 정렬한다.

이렇게 하면 가장 적은 금액부터 차례대로 예산을 소모할 수 있게 된다.

 

2. 총 합 계산: while budget < sum(d): d.pop()

배열 d의 총 합을 계산한다.

만약 이 총 합이 주어진 예산budget보다 크다면 예산을 초과하게 되므로, 배열의 가장 큰 값을 하나씩 제거합니다.

 

3. 반복 제거:
배열의 가장 큰 값을 pop()하는 것은, 현재 배열의 총 합이 예산을 초과할 경우 가장 큰 값을 제거함으로써 예산 내에서 지원할 수 있는 부서의 수를 줄이는 역할을 한다.

배열의 가장 큰 값을 제거하면 총 합이 감소하게 되어 예산 내에 맞출 수 있게 된다.

 

결과 반환: return len(d)

최종적으로 배열의 길이는 예산 내에서 지원할 수 있는 최대 부서 수를 의미한다.

 

예시

입력:

d = [1, 3, 2, 5, 4]
budget = 9

과정:

1. 배열 d를 오름차순 정렬.

   d = [1, 2, 3, 4, 5]

2. 현재 총 합은 1 + 2 + 3 + 4 + 5 = 15이며, 이는 예산 9를 초과한다. 따라서 가장 큰 값 5를 제거.

   d = [1, 2, 3, 4]

3. 다시 합을 계산하면 1 + 2 + 3 + 4 = 10이며, 여전히 예산 9를 초과한다. 따라서 가장 큰 값 4를 제거.

   d = [1, 2, 3]

4. 이제 합은 1 + 2 + 3 = 6이며, 이는 예산 9 내에 있으므로 멈춘다.
5. 최종 배열 길이는 3이므로, 최대 3개의 부서를 지원할 수 있다.

결과:

print(solution(d, budget))  # 출력: 3

 

핵심 정리

• 배열을 정렬하여 가장 적은 금액부터 예산을 소모하게 한다.
• 총 합이 예산을 초과하면 가장 큰 값을 반복적으로 제거하여 예산 내에 맞춘다.
• 최종 배열의 길이는 지원할 수 있는 최대 부서 수를 의미힌다.

이 방법은 그리디 알고리즘을 사용하여, 가능한 많은 부서를 예산 내에서 지원할 수 있는 최적의 방법을 찾는다.

 

 

 

 

회고

문제를 잘못 읽고 합이 budget과 같아야만 하는 줄 알고 헤맸다

문제를 똑바로 읽자