[Greedy] 최소 개수의 동전으로 거스름돈 주기

동전의 종류 : 500원, 100원, 50원, 10원, 5원

k원의 거스름돈을 입력받았을때, 동전의 개수를 최소화 하여 거스름돈을 주는 알고리즘을 구현한다.

 

나의 코드

function partTimeJob(k) {
  // 동전의 개수 cnt = 0;
  // 500으로 나눈다. 만약 나머지가 없으면, cnt에 몫을 더하고 종료
  // 나머지가 있다면, 나머지 버리고 몫을 cnt에 더하기
  // (k - 500 * cnt) / 100... 반복

  let cnt = 0;

  // return 문이 있어야 진행이 중단됨
  // 동전 값으로 거스름돈을 나눴을때 정수값이 나오면 중단
  // 정수값이 나오지 않으면, 더 작은 동전을 이용한 거스름돈을 계산

  if(Number.isInteger(k/500)){
    return cnt = cnt + k/500 
  }else if (!Number.isInteger(k/500)){
    cnt = cnt + Math.floor(k/500)
    k = k - 500 *  Math.floor(k/500)
  }

  if(Number.isInteger(k/100)){
    return cnt = cnt + k/100
  }else if (!Number.isInteger(k/100)){
    cnt = cnt + Math.floor(k/100)
    k = k - 100 *  Math.floor(k/100)
  }
  
  if(Number.isInteger(k/50)){
   return cnt = cnt + k/50
  }else if (!Number.isInteger(k/50)){
    cnt = cnt + Math.floor(k/50)
    k = k - 50 * Math.floor(k/50)
  }

  if(Number.isInteger(k/10)){
    return cnt = cnt + k/10
  }else if (!Number.isInteger(k/10)){
    cnt = cnt + Math.floor(k/10)
    k = k - 10 *  Math.floor(k/10)
  }

  if(Number.isInteger(k/5)){
    return cnt = cnt + k/5
  }else if (!Number.isInteger(k/5)){
    cnt = cnt + Math.floor(k/5)
    k = k - 5 *  Math.floor(k/5)
  }
  return cnt + k;
}

reference

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

레퍼런스 코드가 더 간결한 이유?

반복되는 부분을 캐치하여 반복문으로 처리를 했다.

내가 고쳐야 할 부분

수도 코드를 작성해놓고, 그에 기반하여 코드를 작성해야 한다.

(나는 수도코드를 작성해놓았지만 정작 코드는 따로 작성을 함)

반복되는 부분을 잘 잡아내서 어떻게 반복문으로 처리할지 고민한다.