편의점 알바

문제

편의점에서 아르바이트를 하고 있는 중에, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이 부족하다는 것을 알게 되었습니다.
현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.
동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.

입력

인자: k
number 타입의 k
1 <= k <= 100,000,000

출력

number 타입의 거스름돈 K원을 만드는데 필요한 동전 개수의 최솟값을 반환해야 합니다.

나의 풀이(1)

무작정 풀려고만 하다보니까 하드코딩을 했다. for 반복문과 if 조건문을 사용하면 간단하게 코드를 짤 수 있었는데 while 문으로만 하려다보니 코드가 지저분해졌다.

그리고 500원,100원, ... 1원 각각의 개수는 필요가 없는데, 각각을 모두 구하기 위해 불필요한 변수를 5개나 선언했다.

function partTimeJob(k){
  const arr = [500, 100, 50, 10, 5, 1];
  
  let sum = k;
  if(sum%arr[0]===0) return sum/arr[0];
  let coin500, coin100, coin50, coin10, coin5, coin1;
  
  while(sum>0){
    coin500 = Math.floor(sum/arr[0]);
    sum = sum - arr[0]*coin500;
    
    coin100 = Math.floor(sum/arr[1]);
    sum = sum - arr[1]*coin100;
    
    coin50 = Math.floor(sum/arr[2]);
    sum = sum - arr[2]*coin50;
    
    coin10 = Math.floor(sum/arr[3]);
    sum = sum - arr[3]*coin10;
    
    coin5 = Math.floor(sum/arr[4]);
    sum = sum - arr[4]*coin5;
    
    coin1 = Math.floor(sum/arr[5]);
    sum = sum - arr[5]*coin1;
  }
  return coin500+coin100+coin50+coin10+coin5+coin1;
}

나의 풀이(2)

첫번째 풀이법에서 반복되는 코드를 최대한 줄여보았다. cnts라는 배열을 선언해 1,5,10,100,500원 개수를 push해주고 마지막에 reduce 메소드를 써서 합친 값을 리턴했다.

그런데, 레퍼런스 코드를 보니 let total = 0을 활용해서 누적해서 더해주는 방법이 더 간단한 것 같다.

function partTimeJob(k){
  const arr = [1, 5, 10, 50, 100, 500];
  let cnts = [];
  for(let i=arr.length-1; i>=0; i--){
    if(k>0){
      const cnt = Math.floor(k/arr[i]);
      k = k - arr[i]*cnt;
      cnts.push(cnt);
    }
  }
  return cnts.reduce((acc,cur)=>{
    return acc + cur;
  },0);
}  

레퍼런스

function partTimeJob(k){
  const arr = [500, 100, 50, 10, 5, 1];
  let total = 0;
  
  for(let i=0;i<arr.length;i++){
    if(k>0){
      const cnt = Math.floor(k/arr[i]);
      k = k - arr[i]*cnt;
      total = total + cnt;
    }
  }
  return total;
}