[프로그래머스 | JS] lv.1 예산

[문제 설명]: 부서별로 물품을 구매하는데 필요한 금액을 담은 배열 d와 전체 예산 budget을 매개변수로 준다. 

전체 예산은 정해져있고 모든 부서의 물품을 구매해줄 수는 없으며 최대한 많은 부서의 물품을 구매해 줄 수 있도록 해야 한다. 

 

[제한 사항]

• 전체 부서의 개수는 1이상 100이하 => i = 0; d.length < 100 까지
• d의 각 원소는 부서 별로 신청 금액이다. 1이상 100,000이하의 자연수 (양의 정수)
• budget 1이상 10,000,000 이하의 자연수 (양의 정수)

[문제 풀이 방법]

1. 배열의 원소가 랜덤으로 들어가 있지만 양의 정수라는 점을 고려하여 작은 원소부터 budget에서 삭감해가면 최대한 많은 부서의 지원이 가능 => array.sort() 를 활용하여 오름차순 정렬 
   • array.sort() 의 기본 콜백은 오름차순 정렬이 아니라 문자열 순서대로 정렬되는 것이므로 콜백함수의 인자를 활용하여 오름차순임을 명시해줘야 한다. (a,b) => a - b
2. 오름차순 정렬된 배열 d를 for문에 위의 범위로 순회하면서 budget이 0이되는 시점에 break; 후, answer를 return 한다. 
   • 처음에는 sort()한 배열에 reduce를 사용하려고 했으나 early return이 불가능, 즉 배열의 끝까지 전부 순회해야하기 때문에 비효율적이다. 또한, break도 안된다. early return 을 하려면 reduce의 4번째 인자인 arr전체를 splice()를 통해 조작하여 하는 방법이 있으나 for문을 활용하는 것이 효율적으로 판단되어 변경
   • 현재 d[i] 와 남은 budget의 값이 동일할 경우 return 해줘야 하는 값에 대해 쓸데 없는 분기가 발생하여 answer과 sum 변수를 생성함

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

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

      if (sum > budget) {
        answer--;
        break;
      }
    }
    return answer;
  }
  // console.log(solution([2, 2, 3, 3], 10)); 디버깅용

 

[다른 사람 풀이]

1. while과 reduce, pop() 조합을 쓴 솔루션도 있었지만 while의 조건식에서 reduce를 계속 호출하는 것은 비효율적이라고 생각했음

 

2. while의 조건식으로 내가 변수로 빼놓은 sum과 budget을 비교하여 true가 된 시점까지 index를 증가시켜주고 sum인 `answer + d[index] `가 budget 보다 커졌을 경우, 조건문을 종료하고 index를 return 하는 식을 발견했고 내 식보다 깔끔하고 명시적으로 보인다. index를 로컬 변수로 잡는 것을 생각하지 못했다.

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

    //while을 사용하지만 내부적으로 reduce를 사용하지 않기 떄문에 이 코드가 더 효율적으로 보인다.
    while (answer + d[index] <= budget) {
      answer += d[index];
      index++;
    }
    return index;
  }