코딩테스트 #33 예산

문제

풀이

핵심은 d배열 안 원소 몇 개의 합이 budget에 들어갈 수 있냐인데
배열의 원소를 최대한 많이 구겨넣으려면, 작은 것 순으로 넣어보는 것이 가장 편합니다.

그래서 먼저 정렬을 해주고, budget의 범위 안이면 더해주는 작업을 했습니다.
사실 이것보다 d 배열의 원소로 budget에 가까운 가장 큰 수를 만드는 것을 했으면 조금 더 어려웠지 않나 싶습니다.

아래의 정답 코드에는 약간의 비효율이 있긴 한데 O(n)의 시간에 돌아갑니다.
비효율을 없애려면 for문을 작성하고 원소를 다 찾은 시점에 break를 걸면 됩니다.

let solution = (d, budget) => {
    let answer = 0;

    d.sort((b, a) => b - a).reduce((a, c) => {
        if(a+c <= budget) {
            answer++;
            return a+c;
        }
    }, 0);

    return answer;
}