[LeetCode] 860. Lemonade Change

leetcode.com/problems/lemonade-change/

Lemonade Change - LeetCode

내가 고른 문제인데, 결국 못풀었다.

테스트케이스가 적은 경우에는 정상 작동하는데, 커지면 안되는 걸 보면 로직 어딘가 구멍이 있다는 뜻이겠지..?

근데 어디서 잘못된건지 도통 눈치를 못채겠다.

스터디 시간에 물어봐야겠다...😅

 

each lemonade costs $5
Customers are standing in a queue to buy from you, and order one at a time
=> 순서대로 주문 (한 번에 하나씩)
Each customer will only buy one lemonade => 한 개의 레몬에이드만 구매 가능
pay with either a $5, $10, or $20 bill
net transaction 순 거래
Note that you don't have any change in hand at first. 
=> 처음에는 잔돈 없음 => 첫 구매 손님이 $5가 아니라면 false
Return true if and only if you can provide every customer with correct change.

 

해시맵으로 풀 수 있을 것 같아서 처음에는 map 저장을 {인덱스 : 달러} 형식으로 했었는데

20 달러일때 조건문이 도저히 정리가 안돼서 다른 사람 코드를 보고 힌트를 얻었다. 저번 풀이부터 해시맵의 굴레에 빠져버린 나..

인덱스 (손님) 하나하나 마다 저장할 필요없이 5달러나 10달러만 저장하면 된다는 사실을 깨달았다.

이래서 처음에 생각을 틀린방향으로 하면 되돌리기가 힘든가보다..💬

 

근데 왜 안되는지 모르겠다..진짜..왜지...

import java.util.HashMap;

public class LemonadeChange0317 {
	
    public static boolean lemonadeChange(int[] bills) {
    	// 처음에는 잔돈 없음 => 첫 구매 손님이 $5가 아니라면 false 
    	if(bills[0]!=5) {
    		return false;
    	}
    	
    	// 1. change map 만들어서 풀기 {달러 : 갯수}
    	HashMap<Integer, Integer> change = new HashMap<Integer, Integer>();
    	int five=0; int ten=0;
    	change.put(5,five);
    	change.put(10,ten);
    	
    	for(int i=0;i<bills.length;i++) {
    		if(bills[i]==5) {
    			// 5 달러 추가
    			change.replace(5,five+=1);
    		} else if(bills[i]==10) {
    			change.replace(10,ten+=1);
    			if(change.get(5)>=1) {
    				change.replace(5,five-=1);
    			}else {
    				return false;
    			}
    		} else {
    			if(change.get(5)>=3) {
    				//1. $5 3장 이상
    				change.replace(5,five-=3);
    			}else if(change.get(5)>=1 && change.get(10)>=1){
    				//2. $5 1장이상 $10 1장 이상
    				change.replace(5,five-=1);
    				change.replace(10,ten-=1);
    			}else {
    				return false;
    			}
    		}
    	} //for
    	
    	return true;
    }
}

스터디하면서 알아냈다. 예외케이스를 생각하지 못해서 틀렸던 것!!!

우선순위를 봤을때 $20를 낸 경우에는 $10를 먼저 소진해야한다.

왜? 

5달러 3장을 먼저 소진하게되면 10달러에 잔돈을 줄 수 있는경우에도 못주게 되는 케이스가 생기니까!

그래서 else문 안에 if 순서를 바꿔줬다. 잘 작동한다.

주어진 테스트케이스 이외의 까다로운 예외 케이스를 항상 먼저 생각해보는 사고능력을 길러야겠다.

class Solution {
	public boolean lemonadeChange(int[] bills) {
		// 처음에는 잔돈 없음 => 첫 구매 손님이 $5가 아니라면 false 
		if(bills[0]!=5) {
			return false;
		}

		// 1. change map 만들어서 풀기 {달러 : 갯수}
		HashMap<Integer, Integer> change = new HashMap<Integer, Integer>();
		int five=0; int ten=0;
		change.put(5,five);
		change.put(10,ten);

		for(int i=0;i<bills.length;i++) {
			if(bills[i]==5) {
				// 5 달러 추가
				change.replace(5,five+=1);
			} else if(bills[i]==10) {
				change.replace(10,ten+=1);
				if(change.get(5)>=1) {
					change.replace(5,five-=1);
				}else {
					return false;
				}
			} else {
				if(change.get(5)>=1 && change.get(10)>=1) {
					//2. $5 1장이상 $10 1장 이상
					change.replace(5,five-=1);
					change.replace(10,ten-=1);
				}else if(change.get(5)>=3){
					//1. $5 3장 이상
					change.replace(5,five-=3);
				}else {
					return false;
				}
			}
		} //for

		return true;
	}
}

💡 여기서 궁금한 점

 

1. 메서드 시작부분에 첫 금액이 $5 달러가 아닌 경우 바로 리턴해주었는데

왜 Runtime이나 메모리 면에서 성능차이가 없는걸까?

 

위 코드에서는 써주나 마나 의미가 없다.

왜냐하면 1. 위에서 미리 return 되는 경우나 2. if문에들어갔을 때 return 되는 경우나 어차피 한번에 빠져나오기 때문이다. 만약에 케이스가 정형화되어있지 않고, for문에서 여러번을 돌아야 return 되는 경우에는 위에 선언해주는게 유의미하겠지만 이번 경우에는 그렇지 않으므로 안쓰는게 오히려 더 좋다고 한다.

유의미한 역할을 하지 않으니까.. 더 간단히 쓰는게 코드 가독성 + 다른사람에게 설명할 때 + 유지보수 에 더 좋기때문..!!

 

2. 리턴되지 않는 if문에 continue; 를 쓸 때와 안 썼을 때 차이가 있을까?

 

현재 작성된 코드에서는 if / else if / else 문으로 묶여있기 때문에  continue;가 유의미한 역할을 다하지 못한다.

오히려 지금 코드에서는 continue;를 빼주는 것이 더 낫다고 한다.

그럼 continue; 는 언제쓸까?

위 상황과 달리 if / if / if 이런식으로 작성된 코드의 경우

해당 if문 이후의 로직을 실행하지 않아도 될때 continue;를 써주는 것이 좋다고 한다.

 

---

보편적인 정답

해시맵을 사용할 필요도 없었다😂

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

        return true;
    }
}

 

---

정답을 보면 아주 간단한 문제였지만, 코딩테스트를 풀면서 빠질수 있는 함정이나 어떤 구문을 언제, 왜 쓰는지에 대해서 좀 더 깊게 알아 볼 수 있어서 좋았다. 코테를 풀면서 가장 힘든게 처음의 풀이사고를 벗어나서 생각하는 것인데, 이건 계속해서 연습이 필요하다. Hashmap이나 어떤 자료구조로 풀어야한다는 강박을 벗자..! 그래도 HashMap의 replace 함수를 써보는 좋은 경험이었다고 생각한다. 오늘의 Special Thanks To ✨예지님✨ 속시원한 설명덕에 진짜 많이 배웠다. 👍