[leetcode] 860. Lemonade Change

❗❗ 해당 문제는 JAVA 로 풀었습니다.

http://leetcode.com/problems/lemonade-change/

문제

레모네이드 판매대에서, 레모네이드 한 개당 가격은 5달러입니다.

고객들은 당신에게서 구입하기 위해 줄을 서서, 한 번에 하나씩 주문합니다(bills 순서대로).

각 고객은 레모네이드를 한 개만 구입하고 5, 10달러 또는 20달러 지폐로 지불합니다.

각 고객에게 올바른 거스름돈 을 제공해야만 고객이 5달러를 지불하게 됩니다.

처음에는 가지고 있는 잔돈이 없습니다.

모든 고객에게 올바른 거스름돈을 제공할 수 있는 경우에만 true로 반환하세요.

 

예시

Example 1:

Input: 
[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.

처음 3명의 고객으로부터 5달러짜리 지폐를 3장 받은상태. 
네 번째 고객으로부터 10달러짜리 지폐를 모아서 5달러를 돌려줌.
다섯 번째 고객으로부터 10달러 지폐와 5달러 지폐 줌.
모든 고객과의 거래가 잘 성사되었기에, true. (거스름돈 이 정상적으로 잘 전달 됨)

 

Example 2:

Input: 
[5,5,10]
 
Output: 
true

 

Example 3:

Input: 
[10,10]
 
Output: 
false

 

Example 4:

Input: 
[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't give change of $15 back because we only have two $10 bills. Since not every customer received correct change, the answer is false.

처음 2명의 고객으로부터 5달러짜리 지폐를 두 장씩 받음.
다음 2명의 고객은 10달러를 내므로 각각 5달러씩 거스름돈을 줌.
마지막 손님의 경우 10달러 지폐가 두 장밖에 없기 때문에 15달러를 돌려줄 수 없음.
모든 고객과의 거래가 잘 성사되지 않음, false. (거스름돈 이 정상적으로 잘 전달 되지 않음)

 

참고

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

문제

class Solution {
    public boolean lemonadeChange(int[] bills) {
        
    }
}

 

---

내 풀이

우선 차근차근 어떻게 풀어나갈지 생각해보았다.

레몬에이드 5
구매자는 5 10 20 만 지불 가능
거스름돈은 5 10 으로만 줄 수 있음
예를들어 구매자가 20 지불하면 5 10 / 5 5 5 줌

    
1) 처음에는 5만 받아야 함. 그게 아니면 return false
2) 5와 10이 둘 다 가지고 있지 않으면 20을 받지 않음 return false
3) 10을 받으면 가지고있는 돈에서 5를 빼야함.
4) 5를 받으면 나는 5가 ++
ex) 5 10 10 → false

 

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

        if(bills[0]!=5) return false;

        for(int i=0; i<bills.length; i++) {
            if(bills[i]==5) {
                five++;
            }else if(bills[i]==10) { 
                if(five>0) {
                    ten++; five--;	    				
                }else {
                    return false;
                }
            }else { //20
                if(five>=3 && ten==0) {
                    five-=3;
                }else if(ten>=1 && five>=1) {
                    ten-=1; five-=1;
                }else {
                    return false;
                }
            }
        } //for
	return true;
    }
}

 

+) if(five<=0) return false

ten++; five--; 로 바꾸어도 좋은것 같다.

 

직접 풀이

판매자가 거스름돈을 지불할 수 있는 돈을 각각 five, ten으로 변수를 두었다.

 

처음에는 가진게 없으므로 5달러는 0, 10달러는 0 → five=0, ten=0

 

만약 처음 받은 돈이 5달러가 아니라면 거스름돈을 줄 수 없으므로 false

 

구매자에게 5달러를 받았으면 five++;

 

구매자에게 10달러를 받았을때, 내가 5달러를 1개라도 가지고있으면 거스름돈을 줄 수 있으므로 five--; 10달러를 받았으니 ten++; 만약 five<0 이라면 거스름돈을 줄 수 없으므로 false

 

구매자에게 20달러를 받았을때 ( 구매자는 5, 10, 20달러만 줄 수 있으므로 그냥 else 처리 했다. )

거스름돈으로 5달러를 3개 주는것과 5달러 1개, 10달러 1개 로 주는 기준이 애매해서

내 기준으로 10달러가 1개라도 가지고있지 않을때는 5달러 3개를 주는걸로 기준을 잡았다.

 

 

의문점

처음에 아무 생각 없이 bills[i]==10 부분에서 five를 고려하지 않고 ten++; five--; 만 처리해주었는데 Success 나왔었다.

집으로 돌아와서 다른 사람의 코드들을 보니까 five>0 처리를 해주었고 나또한 이게 맞다고 생각했다.

근데 왜 Error가 안뜬거지..? 😓

 

 

 

---

코테 문제를 2번째 풀어본거라 시간도 많이 걸리고 갈피를 잡기 어려웠었지만 넘 재밌었다 😋

이렇게 좋은 문제를 같이 풀자고 권유해준 스터디원들 너무 고맙다구 ~~ 👍👍👍