LeetCode [860]: Lemonade Change

📌 LeetCode [860]: Lemonade Change

🔗 문제 링크

---

문제 설명 📄

레모네이드를 판매하면서 고객이 지불한 금액에 대해 거스름돈을 정확히 제공할 수 있는지 확인하는 문제입니다.

• 레모네이드 가격은 5달러입니다.
• 고객이 (5), (10), (20) 달러 지폐 중 하나를 지불합니다.
• 거스름돈은 항상 적은 수의 지폐를 우선적으로 사용해야 합니다.

입력: 지폐 배열 bills
출력: 거스름돈을 정확히 줄 수 있으면 True, 그렇지 않으면 False

---

문제 접근 방식 📋

1. 현금 관리:
   • (5)달러와 (10)달러 지폐의 개수를 money 딕셔너리로 추적합니다.
2. 조건 처리:
   • (5)달러 지폐: 추가만 하면 됩니다.
   • (10)달러 지폐: (5)달러로 거스름돈을 제공합니다.
   • (20)달러 지폐:
     • (10 + 5)달러로 거스름돈을 주거나, (5 \times 3)달러로 제공합니다.
3. 거스름돈 부족:
   • 지불 가능한 지폐가 부족하면 즉시 False를 반환합니다.
4. 모든 고객 처리 후:
   • 거스름돈을 정확히 제공할 수 있으면 True를 반환합니다.

---

Solution 💻

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        money = {5: 0, 10: 0}

        for bill in bills:
            if bill == 10:
                if money[5] < 1:
                    return False
                money[10] += 1
                money[5] -= 1
            elif bill == 20:
                if money[5] >= 1 and money[10] >= 1:
                    money[5] -= 1
                    money[10] -= 1
                elif money[5] >= 3:
                    money[5] -= 3
                else:
                    return False   
            else:
                money[5] += 1

        return True

시간 복잡도 분석 ⏲️

• 반복문: (O(n)), (n)은 bills 배열의 길이.
• 총 시간 복잡도: (O(n)).

공간 복잡도 분석 🗄️

• 딕셔너리 사용: (O(1)), 고정된 크기의 money 딕셔너리.
• 총 공간 복잡도: (O(1)).

---