[알고리즘] 예산 (부제: How to early break reduce())

프로그래머스 챌린지 중 예산 문제를 풀어보았다.

➡️ 문제링크

간단히 설명하면 한정된 예산으로 가장 많은 팀에 지원비를 줄 수 있는 경우의 수를 구하는 문제다. for문을 통해 해결할 수 있겠다는 생각이 가장 먼저 들었지만, 늘 for문만 쓰는 거 같아서 연습할 겸 reduce를 사용해보았다.

일단 [1,3,2,5,4] 처럼 각 팀이 필요한 지원비가 담긴 d라는 배열을 받는데, 가장 많은 팀에 지원비를 주기 위해 sort()를 이용해 적은 지원비가 필요한 순서대로 정렬했다.

그런데 reduce()를 이용해서 배열의 인자들을 더하는 거까진 좋았는데, reduce는 for문처럼 break를 할 수가 없었다. 구글링을 해보니 splice를 이용해 break처럼 일정 조건을 만족하면 멈추는 것처럼 흉내낼 수 있는 방법이 있었다.

➡️ 참고

다만 splice를 사용할 경우 원본 배열을 건드리기 때문에, slice(0)으로 원본 배열을 복사하는 과정이 선행되어야 했다.

최종 코드는 다음과 같다.

function solution(d, budget) {
    let overBudget = [];
   d.sort((a,b) => a-b) 
    .slice(0) 
    .reduce(function (acc, curr, idx, arr) {
        if(acc+ curr > budget){ return overBudget = arr.splice(idx)}
		  return acc + curr;
		}, 0)
    
    return d.length - overBudget.length;
}

(저 코드를 실행했을 때, overBudget에는 예산을 초과해 지원금을 줄 수 없는 숫자들이 배열로 담긴다.)

물론 이 방식보다 깔끔하고 좋은 방법이 많겠지만, 개인적으로 이 방식으로 해결하려고 시도해보면서 reduce()라는 메소드를 공부하고, 조건을 만족하면 멈추는 것까지 응용해볼 수 있어서 좋았다.