(프로그래머스) 예산

문제를 읽자마자 이분탐색과 재귀를 이용하여 풀어보고 싶었다.
문제해결단계의 설계는 이랬다.

1. 인자로 받은 신청금액의 배열 d의 합이 지원금액 budget보다 작거나 같은 경우는 d.length를 return하고 종료.
2. 그렇지 않다면 신청금액을 sort로 정렬, slice로 새로운 halfArr과 잘리고 남은 배열 restArr을 생성.
3. 만약 halfArr의 모든 요소의 합이 지원금액보다 작다면,
   --halfIsSmall() 재귀실행->
   --3-1. restArr을 다시 반을 잘라서 halfArr과 자른 restArr의 앞부분을 합친다.
   --3-2. 그리고 합쳐진 요소가 지원금액보다 클때까지 재귀실행,
   --3-3. 커지면 재귀종료조건 달성하고, 다시 배열금액의 합이 지원금액보다 작아질때까지 lastIndex를 제거반복, 조건 달성시 배열.length 리턴
4. else 지원금액보다 크다면,
   halfIsBig() 재귀실행->
   반대로 halfArr을 반으로 잘라가면서 재귀실행

코드는 이렇다.

function solution(d, budget) {
    let sum = d.reduce((a,b)=>a+b);
    if(sum <= budget) return d.length;
    
// 함수선언 영역
    const arrSlice = (origin)=>{
    //배열을 반으로 잘라 반과 나머지배열을 각각 return해주는 함수
        const halfArr = origin.slice(0, Math.ceil(origin.length/2));
        const restArr = origin.slice(Math.ceil(origin.length/2));
        return [halfArr, restArr];
    }

    const halfIsSmall = (half, rest)=>{
        let standard = half.reduce((a,b)=>a+b);
        let result = half.length;
        if(standard > budget){
            while(standard > budget){
                standard -= half[result-1];
                result--;
            }
            return result;
        }else{
            [halfArr, restArr] = arrSlice(rest);
            const halfPlusRest = half.concat(halfArr);
            return halfIsSmall(halfPlusRest, restArr);
        }

    }
    const halfIsBig = (half, rest)=>{
        let standard = half.reduce((a,b)=>a+b);
        let result = half.length;
        if(standard < budget){
            while(standard < budget){
                standard += rest[0];
                result++;
            }
            return result-1;
        }else{
            [halfArr, restArr] = arrSlice(half);
            const restPlusHalf = rest.concat(restArr);
            return halfIsBig(halfArr, restPlusHalf);
        }
    }
    
    
    // 코드시작, 정렬된 sortArr의 halfArr 총 합이 지원금액보다 작다면
    // halfIsSmall 재귀함수 실행
    // 크다면 HalfIsBig 실행,
    let sortArr = d.sort((a,b)=>a-b);
    [halfArr, restArr] = arrSlice(sortArr);
    const halfsum = halfArr.reduce((a,b)=>a+b);

    if(halfsum === budget) return halfArr.length;
    else if(halfsum < budget) return halfIsSmall(halfArr, restArr);
    else return halfIsSmall(halfArr, restArr);
}

제출할 때는 arrSlice라는 함수를 사용하지 않고
조건문안에서 직접 slice시켜주고 했는데, 중복되는 부분이 눈에 거슬리고
이렇게 하면 메모리나 성능문제가 좋아질까 궁금해서 했는데,
테스트케이스 기준으로 17번이 유난히 속도가 오래걸렸는 0.76ms에서 0.34ms으로 두배정도 빨라지고,
그 외엔 들쭉날쭉 (0.10ms~0.35ms)까지 더 빨라지는 경우도 더 느려지는 경우도 있더라.
ceil이냐 floor이냐에 따라서도 조금씩 차이가 날테니 ..
항상 상황에 맞는 베스트를 찾아보자 !