LeetCode | Easy | 860. Lemonade Change

LeetCode | Easy | 860. Lemonade Change

Problems

• 📘 Src: LeetCode
• 🗂️ Cat: Greedy

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

Constraints

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

Examples

bills	Output
[5, 5, 5, 10, 20]	true
[5, 5, 10, 10, 20]	false

Solutions

• ⏳ TC: O(n)
• 💾 SC: O(1)

import java.util.*;

class Solution {

    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;

        for (int bill : bills) {
            if (bill == 5) {
                five++; // $5를 받은 경우
            } else if (bill == 10) {
                if (five == 0) return false; // 거스름돈이 부족한 경우
                five--; // $5로 거스름돈을 준 경우
                ten++;
            } else { // $20를 받은 경우
                if (ten > 0 && five > 0) { // $10와 $5로 거스름돈을 준 경우
                    ten--;
                    five--;
                } else if (five >= 3) { // $5 세 개로 거스름돈을 준 경우
                    five -= 3;
                } else { // 거스름돈이 부족한 경우
                    return false;
                }
            }
        }

        return true;
    }
}

Approaches

이 문제는 그리디 알고리즘을 사용하여 해결할 수 있습니다. 각 고객이 지불하는 금액에 대해 적절한 거스름돈을 줄 수 있는지 확인합니다.

문제를 해결하는 과정은 다음과 같습니다:

• $5, $10 지폐의 개수를 저장할 변수를 초기화합니다.
• 각 고객의 지불 금액을 순회하며 처리합니다:
  • $5 지폐를 받으면 개수를 증가시킵니다.
  • $10 지폐를 받으면 $5 지폐가 있는지 확인하고, 있으면 개수를 감소시키고 $10 지폐의 개수를 증가시킵니다. 없다면 거스름돈을 줄 수 없으므로 false를 반환합니다.
  • $20 지폐를 받으면 두 가지 경우로 나누어 처리합니다:
    • $10 지폐와 $5 지폐가 모두 있는 경우: $10 지폐와 $5 지폐를 각각 하나씩 사용하여 거스름돈을 줍니다.
    • $10 지폐가 없는 경우: $5 지폐 세 개를 사용하여 거스름돈을 줍니다.
    • 위 두 경우 모두 충족하지 않으면 거스름돈을 줄 수 없으므로 false를 반환합니다.
• 모든 고객을 처리한 후 거스름돈을 모두 줄 수 있으면 true를 반환합니다.

이 알고리즘은 각 고객의 지불 금액을 한 번씩 순회하므로 시간 복잡도는 O(n)이며, 추가적인 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.

Attempts

처음 시도한 접근 방법은 각 지폐의 개수를 해시맵에 저장하고, 각 고객의 지불 금액에 따라 적절한 거스름돈을 계산하는 방식이었습니다. 이를 구현한 코드는 아래와 같습니다:

import java.util.*;

class Solution {

    public boolean lemonadeChange(int[] bills) {
        // 각 지폐의 개수를 저장할 맵 초기화
        Map<Integer, Integer> map = new HashMap<>();
        map.put(5, 0);
        map.put(10, 0);
        map.put(20, 0);

        // 각 고객의 지불 금액을 처리
        for (int bill : bills) {
            if (bill == 5) {
                // $5 지폐를 받은 경우
                map.put(5, map.get(5) + 1);
            } 
            
            else if (bill == 10) {
                // $10 지폐를 받은 경우
                if (map.get(5) == 0) return false; // 거스름돈이 부족한 경우
                map.put(5, map.get(5) - 1); // $5 지폐 하나를 사용하여 거스름돈 제공
                map.put(10, map.get(10) + 1); // $10 지폐 개수 증가
            } 
            
            else if (bill == 20) {
                // $20 지폐를 받은 경우
                if (map.get(10) > 0 && map.get(5) > 0) {
                    // $10 지폐와 $5 지폐가 모두 있는 경우
                    map.put(10, map.get(10) - 1);
                    map.put(5, map.get(5) - 1);
                } else if (map.get(5) >= 3) {
                    // $5 지폐 세 개로 거스름돈을 줄 수 있는 경우
                    map.put(5, map.get(5) - 3);
                } else {
                    // 거스름돈이 부족한 경우
                    return false;
                }
                map.put(20, map.get(20) + 1); // $20 지폐 개수 증가
            }
        }

        return true; // 모든 고객에게 거스름돈을 줄 수 있는 경우
    }
}

이 접근 방식은 정확하게 문제를 해결할 수 있지만, 지폐의 개수를 관리하는 데 있어서 추가적인 공간을 사용합니다. 최적화된 알고리즘은 배열을 순회하며 필요한 지폐의 개수만을 관리하여 공간 복잡도를 O(1)로 줄입니다.