Greedy Algorithm
문제
편의점에서 아르바이트를 하고 있는 중인데, 하필이면 피크 시간대에 손님에게 거스름돈으로 줄 동전이
부족하다는 것을 알게 되었습니다.현재 가지고 있는 동전은 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수도코드
1. 인덱스들은 이미 주어졌기때문에 정렬만 해놓으면 된다.
2. 최대한 적은 수의 동전을 반환해야되기 때문에 가장 금액이 놓은 동전으로 거스름돈을 채운다.
3. 그렇게 채우다가 해당 동전으로 채울 수 없는 지점에 이르면 한단계 적은 금액의 동전으로 채운다.
4. 이런식으로 반복을 진행하면서 거스름돈을 채운다. 그리고 동전을 사용할때마다 카운트를 한다.
5. 최종 동전의 개수를 반환한다.
문제풀이
function partTimeJob(k) {
let coin = [500, 100, 50, 10, 5, 1];
let count = 0;
for(let i = 0 ; i < coin.length ; i++){
while (k >= coin[i]){
k = k - coin[i];
count++;
}
}
return count;
}코드해석
일단 우리가 줄 수 있는 거스름돈 동전의 종류는 정해져 있으니, 이 동전들을 이용해서 배열을 만든다.
그런데 이왕 비교하는거 오름차순이던 내림차순이던 정렬을 해놓는게 계산하기에 편할것이다.
이미 유한한 범위가 있기때문에 sort를 이용하지 않고 변수를 생성할때 수동으로 정렬된 배열을 생성한다.
이 문제에선 내림차순으로 정렬한다.
우리는 동전의 개수가 필요하기때문에 동전을 하나 사용할때마다 카운트를 해줄것이다, 그리고 이 값이
최종 값이 될것이다.
거스름돈으로 반환할 동전이 담겨있는 배열을 순차적으로 탐색한다.
이 식에서 반복문이 두번 들어간다, 그 이유는 한번씩만 반복하지 않기때문이다. 이게 무슨말이냐면
예를들어 우리가 거스름돈을 1300원을 반환해야 하는데 거스름돈 배열을 한번씩만 반복하여 동전들을 하나밖에
사용하지 못한다면 계산식이 성립되지 않는다, 그리고 우리는 최소한의 개수로 반환을 해야하기에
반환해야 할 거스름돈을 최대한 큰 값의 동전으로 채워넣어야 한다, 1300원이라면 500원 2개와 100원 3개
를 배출하면 그것이 최솟값이 된다. 이렇기 때문에 첫번째 인덱스를 탐색할때, 조건식에 성립이 될때까지
반복을 시켜준다. 그 조건은 더이상 해당 동전을 사용할 수 없을때 까지이다.
coin[i] 이 k보다 작거나 같아질때까지 총 거스름돈에서 해당 동전의 가격만큼 빼고 카운트를 준다.
그리고 k보다 작거나 같아지면 반복을 종료하고 다음 인덱스로 넘어간다.
이렇게 모든 반복이 종료되고 카운트 값을 반환한다.
Frontend Developer