🥞 오늘 한 일

• 알고리즘 코드카타
  • 예산

알고리즘 코드카타

문제

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

풀이

STEP 1

function solution(d, budget) {
  let result = 0;
  const sortedD = d.sort((a, b) => a - b);

  for (let i = 0; i < sortedD.length; i++) {
    if (result + sortedD[i] < budget) {
      result += sortedD[i];
    } else if (result + sortedD[i] === budget) {
      return i + 1;
    } else {
      return i;
    }
  }
}

아무렇게나 막 짠 비효율적인 코드... 당연히 통과하지 못 했다. 코드가 쓸데없이 긴 것도 있지만, budget보다 d의 총 합이 작을 경우가 없었기에 문제가 되었다. 때문에 더 효율적으로 짜는 방법을 고민해보았다.

STEP 2

function solution(d, budget) {
  let total = 0;
  let result = 0;
  const sortedD = d.sort((a, b) => a - b);

  for (let i = 0; i < sortedD.length; i++) {
    if (total + sortedD[i] <= budget) {
      total += sortedD[i];
      result++;
    } else {
      break;
    }
  }

  return result;
}

처음에는 forEach문을 사용하여 문제를 풀었으나, for문이 더 성능이 좋다고 하여 for문으로 변경했다. total과 result 변수를 따로 만들어서, total에 i번째 금액을 추가한 금액보다 budget이 크거나 같을 경우 total에 현재까지의 금액을 추가하고 result는 1씩 늘어나도록 설정했다. 그리고 그 외의 조건에서는 budget을 넘어섰다는 의미이므로 break로 반복문을 끝냈다. 그 다음 result를 return 했다.

사실 처음에도 접근 방식이 완전히 잘못되었던 것은 아니었지만 return을 굳이 그 안에서 해줬다는 점, 굳이 여러 케이스를 다루려 했다는 점이 문제였다. 조금만 더 생각하면 간결한 코드를 작성할 수 있기에, 알고리즘을 앞으로도 더욱 많이 풀어야할 것 같다.