문제 정의
숫자 배열 arr을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.
다음과 같은 상황을 가정해 보겠습니다:
어느 가게 주인이 정확히 5원짜리(₹5) 상품 하나를 판매하고 있습니다. 손님들이 줄을 서서 각각 이 상품을 한 개씩 구매하려고 하는데, 손님들은 가게 주인에게 5원(₹5), 10원(₹10) 또는 20원(₹20) 짜리 지폐를 낼 수 있습니다. 가게 주인은 처음에 돈을 한 푼도 가지고 있지 않으며, 배열은 줄에 선 손님들이 내는 지폐를 순서대로 나타냅니다.
우리의 함수는 가게 주인이 모든 손님에게 정확한 거스름돈을 지급할 수 있는지 여부를 판단해야 합니다.
예를 들어, 함수의 입력이 다음과 같다면:
입력
const arr = [5, 5, 10, 10, 20];
출력
const output = false;
출력 설명
두 장의 5원 지폐가 두 명의 10원 지폐를 낸 손님에게 거스름돈으로 사용되고 나면, 마지막에 20원 지폐를 낸 손님에게 거스름돈을 만들어 줄 수 없기 때문입니다.
풀이 접근 방식
이 문제는 그리디(Greedy) 알고리즘으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다:
- 손님이 5원을 내면: 거스름돈이 필요 없으므로 5원 지폐 개수를 1 증가시킵니다.
- 손님이 10원을 내면: 5원 지폐 한 장을 거스름돈으로 줘야 하므로, 5원이 없으면 false를 반환합니다. 있다면 5원은 하나 줄이고 10원은 하나 늘립니다.
- 손님이 20원을 내면: 15원의 거스름돈이 필요합니다. 우선 (10원 + 5원) 조합을 시도하고, 없다면 5원 세 장으로 대체합니다. 둘 다 불가능하면 false를 반환합니다.
10원 + 5원 조합을 먼저 사용하는 것이 그리디 전략의 핵심입니다. 5원 지폐는 어떤 거스름돈에도 쓰일 수 있지만 10원 지폐는 20원짜리 거스름돈에만 유용하므로, 10원을 최대한 빨리 소진하는 것이 유리합니다.
예제 코드
다음은 위 로직을 구현한 코드입니다:
const arr = [5, 5, 10, 10, 20];
const provideChanges = (arr = []) => {
let fives = 0
let tens = 0
for(let i = 0; i < arr.length; i++) {
switch(arr[i]) {
case 5:
fives += 1
break
case 10:
if(fives <= 0) {
return false
}
fives -= 1
tens += 1
break
default:
if(tens >= 1 && fives >= 1) {
tens -= 1
fives -= 1
} else if(fives >= 3) {
fives -= 3
} else {
return false
}
break
}
}
return true
};
console.log(provideChanges(arr));출력 결과
false
코드 설명
위 코드에서는 변수 fives와 tens를 사용해 현재 보유한 5원 및 10원 지폐의 개수를 추적합니다. 배열을 순회하면서 각 손님이 낸 금액에 따라 switch 문으로 분기 처리하며, 거스름돈을 줄 수 없는 순간 즉시 false를 반환합니다. 모든 손님에게 거스름돈을 성공적으로 지급했다면 반복문 종료 후 true를 반환합니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)입니다. 여기서 n은 손님 수(배열의 길이)입니다.