[Greedy] 편의점 알바

편의점 알바

문제

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

입력

인자: k

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

출력

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

입출력 예시

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

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

문제풀이

function partTimeJob(k) {
// 동전의 금액을 큰 순서대로 정렬한 배열
  const coins = [500, 100, 50, 10, 5, 1];
  // 각 동전의 개수를 누적할 변수
  let coinCount = 0;
  // 각 동전마다 반복문을 수행하여 동전의 개수를 계산
  for (const coin of coins) {
    // 현재 동전으로 최대한 거슬러 줄 수 있는 개수를 계산
    const quotient = Math.floor(k / coin);
    // 동전의 개수를 누적
    coinCount += quotient;
    // 남은 금액을 계산
    k -= quotient * coin;
  }
  // 거슬러 줄 수 있는 동전의 총 개수 반환
  return coinCount;
}

/* 
function partTimeJob(k) {
  // 동전수, 남은돈
  // 카운트 
	let count = 0;
	const coin = [500, 100, 50, 10, 5, 1]; //-> 1230원
  for(let i of coin){
    count = count + Math.floor(k/i); // 동전의 수
    k = k - i * Math.floor(k/i); // 남은돈
  }
	//count를 리턴합니다.
	return count;
}
*/

레퍼런스코드

/* 레퍼런스 코드 */
function partTimeJob(k) {
  // 결과 변수를 0으로 초기화합니다.
  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 = k - (wallet[i] * sum);
    }
  }
  // 원래 금액 k를 거슬러줄 최소한의 동전 수를 반환합니다.
  return result;
}

레퍼런스 코드 블록은 k라는 금액을 거스름돈으로 거슬러줄 때 최소한의 동전 수를 계산하는 partTimeJob 함수를 구현합니다.

함수 첫 번째 줄에서는 결과를 저장할 변수인 result를 0으로 초기화합니다.

두 번째 줄에서는 사용 가능한 동전의 값들을 배열 wallet에 정의합니다. 가장 큰 동전부터 내림차순으로 정렬되어 있으므로, 가능한 가장 큰 동전을 사용할 수 있게 됩니다.

세 번째 줄에서는 wallet 배열의 모든 동전 값을 반복하는 for 루프를 설정합니다. 이 루프를 통해 k 금액을 거슬러줄 때 최소한의 동전 수를 계산할 수 있습니다.

루프 안에서는 먼저 k가 0보다 큰지 확인합니다. 만약 k가 0이라면 더 이상 거스름돈을 거슬러 줄 필요가 없으므로 루프를 종료합니다.

k가 0보다 크다면, 현재 동전 값을 이용하여 k를 거슬러줄 때 사용할 수 있는 최대 동전 수를 계산합니다. 이를 위해 Math.floor 함수를 사용하여 k를 현재 동전 값으로 나눈 결과를 내림한 값으로 계산합니다. 이렇게 하면 k의 값을 초과하지 않는 최대 동전 수를 구할 수 있습니다.

루프에서는 계산된 동전 수를 result에 추가하고, 해당 동전 값의 가치를 k에서 빼줍니다. 이를 통해 총 동전 수와 k에 남아있는 거스름돈 금액이 갱신됩니다.