[JavaScript] Greedy : 편의점 알바 - 최소한의 동전 개수 구하기

문제

편의점에서 아르바이트를 하고 있는 중에, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이 부족하다는 것을 알게 되었습니다.

현재 가지고 있는 동전은 1원, 5원, 10원, 50원, 100원, 500원으로 오름차순으로 정렬되어 있고, 각 동전들은 서로 배수 관계에 있습니다.

동전 개수를 최소화하여 거스름돈 K를 만들어야 합니다. 이때, 필요한 동전 개수의 최솟값을 구하는 함수를 작성해 주세요.

입력

인자: k

• number 타입의 k
• 1 <= k <= 100,000,000

출력

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

입출력 예시

// 4000원을 받았을 때 500원짜리 동전 8개를 반환합니다.
const output1 = test1(4000);
console.log(output1); // --> 8

// 4972원을 받았을 때 500원짜리 동전 9개, 100원짜리 동전 4개, 50원짜리 동전 1개,
// 10원짜리 동전 2개, 1원짜리 동전 2개, 총 18개를 반환합니다.
const output2 = test1(4972);
console.log(output2); // --> 18

풀이

로직

이 문제를 제대로 이해했다면 친숙함 이전에 당연함마저 느낄 것이다.
만약 우리가 실생활에서 사용하는 동전들을 가지고 900원을 거슬러 줘야 한다면 대부분 500원 1개와 100원 4개를 줄 것이니 말이다.
효율적으로 주는 방법을 자연스럽게 생각하고 고른다.
이 문제는, 그러한 ‘제일 효율적인 방법’을 찾는 ‘그리디(Greedy) 알고리즘’을 이용하여 푸는 문제다.

Greedy Algorethm(탐욕 알고리즘) : 최적해를 구하는 데에 사용되는 근사적인 방법

앞에서 말한 900원을 거슬러 주는 방법을 생각해 보자.
900원짜리 동전이 없으니 900원보다 작은 원화 중에 가장 큰 단위를 생각하게 된다.
그것이 500원이고, 500원으로 900원을 채울 수 있는 만큼 채운다.(=1개)
이후 가장 큰 단위는 100원이므로 100원으로 나머지 400원을 채울 수 있는 만큼 채운다.(=4개)
그러면 채워야 하는 금액이 0원으로 끝난다.
이를 수도코드로 작성해 보자.

1. 갖고 있는 단위들을 가장 큰 순서로 stack 배열을 마련한다.(stack = [500, 100, 50, …])
2. return할 동전 개수를 담을 count를 선언하고 0을 할당한다.
3. for문으로 stack의 요소들을 훑고, 그 요소를 입력 변수 k에 나눠서 몫을 count에 더한다. 이때 parseInt 메소드를 이용한다.
4. 입력 변수 k는 새로운 변수 k2에 재할당한다. 이때 stack[i]값만큼 나눈 다음 나머지를 할당시키면 된다. % 메소드를 이용한다.
5. 1번부터 4번을 for문 다 돌릴 때까지 반복하고 count를 return한다.

해답 코드

function partTimeJob(k) {
  // k=거스름돈
  
  // 1억일 경우 500원으로 나눈 게 답
  // 큰 수인 500부터 차례대로 작은 값으로 나누면서 답을 구하면 된다.
  // % 나머지 연산자를 이용하자.

  let stack = [500, 100, 50, 10, 5, 1];
  let count = 0;
  let k2= k;

  // 4100원을 받으면
  // parseInt(4100 / 500) = 8; => count += 
  // 4100 % 500 = 100 >> parseInt(100/100 >> count+=)

  for(let i=0; i<stack.length; i++){
    let temp = parseInt(k2/stack[i]);
    count += temp;
    k2 = k2 % stack[i];
  }

  return count;
}

기타 - 한마디

최근에 취업을 위한 실무과제에서 거스름돈을 구하는 기술이 사용되는 코딩을 해야 했었다.
당시 이 문제를 풀었던 기억이 나서 이렇게 블로그 포스팅을 하게 되었다.
다시 이렇게 복습하며 머릿속에 제대로 심어놔야겠다.
다음엔 이 문제의 심화.ver도 풀어볼 예정이다!

카카오페이로 커피사기 ❤️ 토스 계좌로 커피사기 ❤️