C++ 860. Lemonade Change(Leet Code)

Leet Code_860. Lemonade Change

Greedy

 

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

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

고객들에게 거스름돈을 주면서 판매가 가능한지 확인하기

​

방법

1. 고객들에게 거스름돈을 주면서 판매가 가능한지 확인하기

 

결과

고객들에게 거스름돈을 주면서 판매가 가능한지 확인하기

 

통과한 코드

class Solution {
public:
 
    unordered_map<int, int> maps;
bool pay(int n)
{
    int pay = n;
    if (n == 5)
    {
        maps[5]++;
        return true;
    }
        
    while (n > 20 && maps.find(20) != maps.end() && maps[20] > 0)
    {
        n -= 20;
        maps[20]--;
    }
    while (n > 10 && maps.find(10) != maps.end() && maps[10] > 0)
    {
        n -= 10;
        maps[10]--;
    }
    while (n > 5 && maps.find(5) != maps.end() && maps[5] > 0)
    {
        n -= 5;
        maps[5]--;
    }
    if (n > 5)
        return false;
    else
    {
        if (pay == 20)
            maps[20]++;
        else if (pay == 10)
            maps[10]++;
        return true;
    }
}
bool lemonadeChange(vector<int>& bills) {
    
    for (int i = 0; i < bills.size(); i++)
    {
        if (pay(bills[i]) == false)
            return false;
    }
    return true;
}
};

성공은 했지만 생각보다 빠르지 않다. 속도를 생각해서 map을 쓴건데..

 

다른 사람 코드

class Solution {
public:
 
  bool lemonadeChange(vector<int>& bills) {
	int fives = 0, tens = 0;
	for (const auto& bill : bills) {
		if (bill == 5)
			fives++;
		else if (bill == 10) {
			tens++;
			fives--;
		}
		else {
			tens--;
			fives--;
			if (tens < 0) {
				tens = 0;
				fives -= 2;
			}
		}
		if (fives < 0)
			return false;
	}
	return true;
}
};

빠르다.

map같은거 안쓰고 그냥 int형 변수 2개로 처리하였다.

다른 사람 코드를 보니 key 20은 필요도 없는데! 왜썼을까

간단한 조건으로 tens와 fives를 처리하면서 구했다.

똑똑해~~~