편의점 알바(Greedy)

문제

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

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

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

입력

인자: k

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

출력

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

입출력 예시

나의 코드

최소한의 개수로 거스름돈을 주기 위해서는 거슬러줘야 할 돈을 가치가 큰 돈부터 나눠야합니다.

갖고있는 동전과 지폐를 내림차순으로 만들고, 이를 반복 순회하면 큰 값부터 연산할 수 있습니다.

먼저, 손님에게 건네줘야 할 거스름돈(k)을 5000원으로 먼저 나눕니다. 예를 들어 5000원으로 나눈 몫이 3이라면, 5000원 지폐 3장을 건네줘야하기 때문에, 결괏값에 그 몫을 더합니다.

5000원 지폐 3장으로 이미 건네줬다면, 거스름돈(k)를 남은 액수로 할당해야합니다. 그 나머지 액수는 5000원으로 나눈 나머지값이 됩니다.

반복 순회를 하며 반복이 종료되면 동전과 지폐의 최솟값을 반환합니다.

결과

소스코드

function partTimeJob(k) {
  // 개수를 세기 위한 변수를 선언합니다.
  let count = 0;
  // 동전과 지폐를 내림차순으로 선언합니다.
  let wallet = [5000, 1000, 500, 100, 50, 10, 5, 1];
  // wallet을 반복 순회합니다.
  for (let i = 0; i < wallet.length; i++) {
    let a = parseInt(k / wallet[i]);
    count += a;
    k = k % wallet[i];
  }
  return count;
}