[CodingTest]Algorithm 예제(Greedy)

Greedy Algorithm - 거스름돈

function keepTheChange(input) {
  //1000엔짜리 지폐를 냈다는 가정이 있고, 입력 값으로는 지불해야 할 금액이 들어옴
  let change = Number(1000 - input);

  let count = 0;

  //입력 값에 배열이 들어오지 않으므로 직접 배열을 만들어줍니다.
  const joiCoins = [500, 100, 50, 10, 5, 1];

  //만든 배열의 개수만큼만 돌려줘야 합니다.
  for (let i = 0; i < joiCoins.length; i++) {
    //거스름돈이 0원이 되면 for문을 멈춥니다.
    if (change === 0) break;

    //거스름돈과 잔돈을 나눈 몫을 카운팅합니다.(쓰인 잔돈의 개수 카운팅)
    count += Math.floor(Number(change / joiCoins[i]));

    //거스름돈을 잔돈으로 나눈 나머지를 재할당합니다.
    change %= joiCoins[i];
  }

  return count;
}