[알고리즘 공부] 배열 내 덧셈 근삿값 경우의 수

https://prpn97.tistory.com/55

[프로그래머스 | JavaScript] 예산

문제를 풀다가, 반복문 안에 여러 내장함수를 넣으면 효율성이 떨어진다는 것을 고려하여

1차원적으로 문제를 다시 풀어보기로 했다. 

 

function solution(d, budget) {
    let count = 0, sum = 0;
    d.sort((a,b) => a - b);

    for(let i = 0; i < d.length; i++){
        count++;
        sum += d[i]

        if(sum > budget)
            count--;
    }
    return count;
}

근삿값이라고 제목을 붙였지만, 이 문제는 budget의 값보다 같거나 작아야 한다. 

기존에 문제를 풀었을 때(위 링크 참조)는 reduce로 다 더하고,

pop을 통해 빼가며 budget보다 작아진 값의 요소의 갯수를 구했다. 

 

동일하게 풀되, 내장함수를 쓰지 않고 풀어보면 다음과 같다. 

경우의 수를 카운트할텐데, 각 요소를 더해가며 sum에 저장하고, 저장할 때마다 1씩 카운트한다.

만약 sum에 저장된 값이 budget보다 커지면 count에서 1을 뺀다. 

 

예를들어 1,2,3,4,5가 d이고 budget이 9일 때 각 요소를 더했을 때 9보다 작거나 같으려면,

순서대로 더해가며 1씩 카운트한다. 카운트에는 총 5가 누적될 것이다. 

그런데, 각 더한 값이 9보다 커지면 카운트는 1씩 차감한다. 

1+2+3은 6인데, 1+2+3+4는 10이다. 5까지 더하면 더 커지므로

4를 더했을 때부터는 카운트가 1씩 차감되므로, 

5에서 2를 뺀 3이 최종적인 카운트 값이 된다.