[LeetCode] Lemonade Change

레모네이드 가판대에서 레모네이드를 5딸라에 팝니다.

고객은 순서대로 레모네이드를 사갑니다.

각 고객은 레모네이드를 하나씩만 사갈 수 있습니다.

고객은 5딸라 10딸라 20딸라를 지불합니다.

주인은 거스름돈을 가지고 있지 않은 상태로 판매합니다.

만약 거스름돈을 돌려줄 수 없다면 false, 마지막 고객까지 거스름돈을 돌려줬다면 true

 

조건

• 0 <= bills.length <= 10000
• bills[i] will be either 5, 10, or 20.

---

Pseudocode (의사 코드)

 

거스름돈을 돌려줄 수 없는 상황이 되면 바로 return false

change 변수 생성
bills 배열 순회
순회하며 5$일 경우 change ++
change가 1이상이고 10$일 경우 change --
change가 3이상이고 20$일 경우 chagne = change - 3
10$ 20$ 경우에 change가 부족하면 return false

---

1차 시도

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int change = 0;
        
        for(int i = 0; i < bills.length; i++)
        {
            if(bills[i] == 5)
            {
                change = change + 1;
            }
            else if(bills[i] == 10)
            {
                if(change < 1) return false;
                change = change - 1;
            }
            else if(bills[i] == 20)
            {
                if(change < 3) return false;
                change = change - 3;
            }
        }
        
        return true;
    }
}
/*
[5,5,5,10,20]
5 0
5 1
5 2
10 3
20 2
*/

 

2차시도 -> 10$와 20$의 경우에도 거스름돈이 여유가 있어 거래가 성사 되면 change를 하나씩 받음

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int change = 0;
        
        for(int i = 0; i < bills.length; i++)
        {
            if(bills[i] == 5)
            {
                change = change + 1;
            }
            else if(bills[i] == 10)
            {
                if(change < 1) return false;   
            }
            else if(bills[i] == 20)
            {
                if(change < 3) return false;
                change = change - 2;
            }
        }
        
        return true;
    }
}

 

문제 다시 파악하기

이 테스트 케이스에서 막힘
[5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,
5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5
,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5
,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5
,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5
,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5
,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5
,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5
,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5
,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5
,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5
,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5
,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5,20,5,10,5
,20,5,10,5,20,5,10,5,20]

10$ 지폐도 거스름돈으로 받아서 거슬러주는 상황을 고려하지 않아서 통과하지 않은것으로 보임

의사코드 재작성

Pseudocode (의사 코드)

거스름돈을 돌려줄 수 없는 상황이 되면 바로 return false

int[] change = {0, 0} 변수 생성 // 5$와 10$보관함
bills 배열 순회
순회하며 5$들어왔을 때  5$++
10$들어왔을때 5$ 1한장이상 보유시 5$-- 10$++
20$ 들어왔을때 5$ 1장 10$ 1장이상 보유시 -> 5$-- 10$--
20$ 들어왔을때 5$ 3장이상 보유시 -> 5$갯수 = 5$ - 3

 

3차시도

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int[] change = {0, 0};
        
        for(int i = 0; i < bills.length; i++)
        {
            if(bills[i] == 5)
            {
                change[0] = change[0] + 1;
            }
            else if(bills[i] == 10)
            {
                if(change[0] < 1){return false;}
                else 
                {
                    change[0] = change[0] - 1;
                    change[1] = change[1] + 1;
                }
            }
            else if(bills[i] == 20)
            {
                if(1 <= change[0] && 1 <= change[1])
                {
                    change[0] = change[0] - 1;
                    change[1] = change[1] - 1;
                }
                else if(3 <= change[0])
                {
                    change[0] = change[0] - 3;
                }
                else
                {
                    return false;
                }
            }
        }
        return true;
    }
}

Runtime: 2 ms, faster than 68.29% of Java online submissions for Lemonade Change.
Memory Usage: 40.1 MB, less than 53.51% of Java online submissions for Lemonade Change.

 

시간복잡도와 공간복잡도의 많은 개선을 할 수 있을것으로 보이므로 추후 개선할 예정

이번주 토요일에 sqld시험이라 sqld공부 해야합니다.

---

leetcode.com/problems/lemonade-change/

Lemonade Change - LeetCode