860. Lemonade Change

문제

---

레모네이드의 가격은 $5입니다. 손님들은 $5, $10, $20을 낼 수가 있는데, $5보다 큰 금액을 내면은  정확한 거스름돈을 줘야합니다. 여기서 명심해야 할 것은 처음에 가지고 있는 거스름돈은 없습니다. Integer array로 bills을 받게 되는데 bills[i]는 i^th 번째 손님이 지불하는 bill을 말합니다. 만약에 고객들한테 정확하게 거스름돈을 줄 수 있으면 true를 반환하고 아니면 false를 반환해야합니다.

 

조건을 보자면 아래와 같이 정리할 수 있는데요.

• 초기에 가지고 있는 거스름돈 없음
• 고객이 낼 수 있는 돈의 종류는 3가지
• 정확하게 거스름돈을 줄 수 있는지 아닌지

풀이

---

푸는 방법은 여러가지 일 수 가 있겠는데요. 처음에 생각나는건 HashMap 이였습니다. key 값에 5,10,20을 저장하고 필요할 때 value의 값이 남아있지 않으면 false. 남아있으면 continue하는 방식으로요. 하지만 Running time이 너무 오래걸리더군요. 그래서 대안으로 생각한게 HashMap 대신 변수 선언으로 해결하는 방법입니다. 풀이는 아래와 같습니다.

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

 

먼저 five와 ten 변수를 선언을 해줍니다. 그리고 bills[i]의 종류에 따라 거스름 돈을 줄 수 있는지 아니면 안 줘도 되는지를 결정하면 됩니다.

 

복잡도

---

Bills을 전체 한 번 다 돌기 때문에 시간 복잡도는 O(n)이 나옵니다. 그리고 변수를 선언한건 five와 ten밖에 없기 때문에 공간 복잡도는 O(1)이 나오게 됩니다.