[LeetCode] 860. Lemonade Change

https://leetcode.com/problems/lemonade-change/description/?envType=daily-question&envId=2024-08-15

leetcode - Lemonade Change

문제 유형 : 그리디

문제 난이도 : Easy

 

문제

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 ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.

 

레몬에이드 스탠드에서, 각 레몬에이드는 5달러이다.

손님은 대기줄을 서고 있다.(bills 배열의 순서대로)

각 손님은 5, 10, 20달러 지폐를 가지고 있고, 당신은 아무 지폐도 없다.

당신은 거스름돈을 거슬러줘야 한다.

거스름돈을 다 거슬러줄 수 있는지 알아내시오.

 

풀이

이 문제는 그리디로 해결할 수 있다.

20달러는 거슬러줄 수 없으므로, 10달러짜리와 5달러짜리의 개수만 세면 된다.

매번 돈을 받을 때마다 지폐의 개수를 누적하고,

거스름돈 값을 구해서 10달러 우선, 5달러를 차선으로 거스름돈을 계산하면 된다.

만약 거스름돈을 주지 못한다면, false를 반환하고, 모든 손님들에 대해 거스름돈 계산이 성공이면 true를 반환하면 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0;
        int ten = 0;

        for(const auto &bill : bills) {
            if(bill == 10) ten++;
            else if(bill == 5) five++;

            int charge = bill - 5;
            while(charge > 0) {
                if(ten && charge >= 10) {
                    charge -= 10;
                    ten--;
                } else if(five && charge >= 5) {
                    charge -= 5;
                    five--;
                } else return false;
            }
        }

        return true;
    }
};

 

 

GO

func lemonadeChange(bills []int) bool {
    var five int
    var ten int

    for _, bill := range bills {
        if bill == 10 {
            ten++
        } else if bill == 5 {
            five++
        }

        charge := bill-5
        for charge > 0 {
            if ten > 0 && charge >= 10 {
                ten--;
                charge-=10
            } else if five > 0 && charge >= 5 {
                five--;
                charge-=5
            } else { return false }
        }
    }

    return true
}