[Algorithm] 편의점 아르바이트 (Greedy)
편의점 알바(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;
}
Author And Source
이 문제에 관하여([Algorithm] 편의점 아르바이트 (Greedy)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@shitaikoto/Algorithm-Greedy2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)