문제 소개
레모네이드 가게가 하나 있다고 상상해 봅시다. 레모네이드 한 잔의 가격은 5달러이며, 손님들은 줄을 서서 한 번에 한 명씩 차례대로 구매합니다.
각 손님은 레모네이드를 한 잔만 구매할 수 있고, 5달러, 10달러, 20달러 지폐 중 하나로 결제합니다. 판매자인 우리는 모든 손님에게 정확한 잔돈을 돌려주어야 하며, 결과적으로 각 손님의 실질 지불 금액이 5달러가 되도록 거래를 마무리해야 합니다. 단, 처음에는 손에 든 잔돈이 하나도 없습니다.
따라서 우리가 확인해야 할 것은, 모든 손님에게 올바른 잔돈을 제공할 수 있는지 여부입니다.
예시로 이해하기
입력이 [5, 5, 5, 10, 20]이라면 결과는 True입니다. 앞의 세 명의 손님에게서 5달러 지폐 세 장을 받게 되고, 네 번째 손님에게는 10달러 지폐를 받고 5달러를 거슬러 줍니다. 이어서 다섯 번째 손님에게는 10달러 지폐와 5달러 지폐를 합쳐 15달러를 거슬러 줍니다. 모든 손님이 정확한 잔돈을 받았으므로 최종 답은 True가 됩니다.
해결 전략: 그리디 알고리즘
이 문제는 그리디(Greedy) 방식으로 손쉽게 해결할 수 있습니다. 핵심은 현재 보유한 5달러, 10달러, 20달러 지폐의 개수를 계속 추적하는 것입니다. 절차는 다음과 같습니다.
- 초기화: n5 = 0, n10 = 0, n20 = 0
- 반복: bills 배열의 각 지폐 i에 대해 아래를 수행합니다.
- i가 5달러면 → n5를 1 증가
- i가 10달러면 → n10을 1 증가
- 그 외(20달러)면 → n20을 1 증가
- 지폐를 받았는데도 n5가 0이면 → False 반환 (잔돈을 줄 수 없음)
- i가 20달러이고 n10 > 0이며 n5 > 0이면 → 10달러 한 장과 5달러 한 장으로 거스름돈 지급 (n10, n5 각각 1 감소)
- i가 20달러인데 n10이 0이고 n5 < 3이면 → False 반환
- i가 20달러인데 n10이 0이고 n5 ≥ 3이면 → 5달러 세 장으로 거스름돈 지급 (n5에서 3 감소)
- i가 10달러이고 n5 > 0이면 → 5달러 한 장으로 거스름돈 지급 (n5 1 감소)
- i가 10달러인데 n5가 0이면 → False 반환
- 모든 손님을 처리했다면 True 반환
여기서 중요한 포인트는 20달러를 받았을 때 가능하다면 '10달러 + 5달러' 조합을 우선 사용한다는 것입니다. 5달러 지폐는 어떤 상황에서도 가장 활용도가 높으므로 최대한 아껴 두는 것이 이 그리디 전략의 핵심입니다.
파이썬 구현 코드
class Solution:
def lemonadeChange(self, bills):
n5 = 0
n10 = 0
n20 = 0
for i in bills:
if i == 5:
n5 += 1
elif i == 10:
n10 += 1
else:
n20 += 1
if len(bills) > 0 and n5 == 0:
return(False)
if i == 20 and n10 > 0 and n5 > 0:
n10 -= 1
n5 -= 1
elif i == 20 and n10 == 0 and n5 < 3:
return(False)
elif i == 20 and n10 == 0 and n5 >= 3:
n5 = n5 - 3
if i == 10 and n5 > 0:
n5 -= 1
elif i == 10 and n5 == 0:
return (False)
return(True)
ob = Solution()
print(ob.lemonadeChange([5, 5, 5, 10, 20]))
입력
[5, 5, 5, 10, 20]
출력
True
복잡도 분석
배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 지폐 개수를 저장하는 변수 몇 개만 사용하므로 공간 복잡도는 O(1)입니다.
마무리
레모네이드 잔돈 문제는 그리디 알고리즘의 대표적인 입문 예제입니다. 지폐 종류가 5, 10, 20달러로 한정되어 있어 단순한 카운터 변수만으로도 해결할 수 있으며, '큰 단위 지폐를 아껴 쓴다'는 그리디의 기본 원칙을 자연스럽게 익힐 수 있는 좋은 연습 문제입니다.