[코딩연습] LeetCode Lemonade Change 거스름돈 나눠주기

LeetCode 문제 중 난이도 Easy인 Lemonade Change이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

  문제해석

레몬에이드 가판대에서 각 레몬에이드의 가격은 $5이다.

레몬에이드를 사기 위해 줄에 선 손님들은 순서대로 한명씩 주문한다. 각각의 손님들은 $5, $10, $20 셋 중에 하나의 지폐를 내고 레몬에이드를 하나씩 주문한다. 정확하게 거스름돈을 돌려주어서 순수한 거래는 손님이 $5씩 지불한게 되어야 한다.

처음에 잔돈 없이 시작해서 모든 손님들에게 정확한 거스름돈을 돌려줄 수 있는 경우에만 true를 리턴하라.

가지고 있는 지폐 수를 체크하기 위해서 5달러 지폐의 수는 five, 10달러 지폐의 수는 ten이라는 변수에 넣는다. 20달러는 거스름돈으로 나갈 일이 없으므로 체크할 필요 없다. 5달러 지폐를 받으면 five+1, 10달러지폐를 받으면 ten+1을 해준다.

20달러 지폐를 받은 경우에는 두가지로 나눌 수 있다. 거스름돈을 10+5 합쳐서 줄 수도 있고 만약에 10달러가 없으면 5+5+5로 줄 수도 있다. 가지고 있는 5달러와 10달러 지폐가 음수가 되는 때가 있다면 거스름돈을 정확하게 돌려줄 수 없는 것이다.

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five=0, ten=0;
        
        for(int b : bills) {
            if(b==5){
                five++;
            }else if(b==10) {
                ten++;
                five--;
            }else if(b==20 && ten==0) {
                five-=3;
            }else{
                ten--;
                five--;
            }
            
            if(five<0 || ten<0) return false;
        }
        
        return true;
    }
}

한가지 유의할 점은 if(five<0 || ten<0) return false는 for문 안에 있어야 한다. 그렇지 않으면 지폐수가 음수였다가 다음 손님들에게 지폐를 받는, 실제로 존재할 수 없는 경우에도 true를 리턴한다.

이 코드의 시간복잡도는 O(n), 공간복잡도는 O(1)이다.

문제 출처 - https://leetcode.com/problems/lemonade-change/