[Leetcode]860. Lemonade Change

📄 Description

At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.

Note that you do not have any change in hand at first.

Given an integer array bills where bills[i] is the bill the $i^{th}$ customer pays, return true if you can provide every customer with the correct change, or false otherwise.

Example 1:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Example 2:

Input: bills = [5,5,10,10,20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can not give the change of $15 back because we only have two $10 bills.
Since not every customer received the correct change, the answer is false.

Constraints:

• 1 <= bills.length <= 105
• bills[i] is either 5, 10, or 20.

🔨 My Solution

문제 해결 포인트!

• $20을 받았을 때 줄 수 있는 거스름돈 종류가 다음 두 가지이다.
  1. $5 한 개 & $10 한 개
  2. $5 세 개
• 위 두 가지 방법 중 어떤 방법을 선택하는 것이 효율적인가? 를 생각해볼 것.

💻 My Submission

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        change=0
        bill_dict={5:0,
                   10:0}
        
        for i in range(len(bills)):
            
            if bills[i]==5:
                bill_dict[bills[i]]+=1
            
            elif bills[i]==10:
                if bill_dict[5]<1: return False
                bill_dict[bills[i]]+=1
                bill_dict[5]-=1
                
            elif bills[i]==20:
                # (5,10) or (5,5,5)
                if bill_dict[5]>0 and bill_dict[10]>0:
                    bill_dict[10]-=1
                    bill_dict[5]-=1
                elif bill_dict[5]>=3:
                    bill_dict[5]-=3
                else: return False
                
                
        return True

💊 Clean Code

    def lemonadeChange(self, bills):
        five = ten = 0
        for i in bills:
            if i == 5: five += 1
            elif i == 10: five, ten = five - 1, ten + 1
            elif ten > 0: five, ten = five - 1, ten - 1
            else: five -= 3
            if five < 0: return False
        return True

💡 What I learned

• 어떤 자료구조에 담을지 잘 판단하기
• 어떻게 하면 readable 한 코드가 될 수 있을지 고민하기
• 중복되는 조건문이 없도록 하기

References

• https://leetcode.com/problems/lemonade-change/
• https://leetcode.com/problems/lemonade-change/discuss/143719/C%2B%2BJavaPython-Straight-Forward