[860] Lemonade Change

주어진 문제

 

 

레모네이드 가격은 한잔에 5달러.

사람들이 레모네이드를 주문할 때 5, 10, 20 달러 중 하나를 택해 값을 치른다. 이때, 주인장(=내)가 돈을 모두 거슬러줄 수 있다면 true, 한 명의 손님에게라도 돈을 거슬러 줄 수 없다면 false를 return 해줘야한다.

 

처음 이 문제를 봤을 때 든 생각은

1. input의 처음은 무조건 5로 시작해야하고(10이나 20으로 시작하면 거스름돈이 없기 때문)
2. input이 5, 10, 20일때 따로 구분해서 해야겠다.
3. 거슬러주기 전에 cashRegister에 돈이 있는지 확인하고
4. 판매하고 받은 돈은 cashRegister에 넣자.

였다.

 

그렇게 처음 작성된 코드는 아래와 같다.

var lemonadeChange = function(bills) {
    if (bills[0] > 5)
        return false;

    let cashRegister = [];

    for (let bill of bills) {
        //5면 cashRegister에 넣고
        if (bill === 5) {
            cashRegister.push(bill);
        }
        //10이면 cashRegister에 10 넣고, 5 빼고
        if (bill === 10)    {
            //cashRegister에 5가 있는지 확인
            let index = cashRegister.indexOf(5)
            //5가 있다면 CashRegister에서 5를 삭제(손님에게 거슬러줌)
            if (index !== -1)
                cashRegister.splice(index, 1);
            else return false;

            cashRegister.push(bill);
        }
        //20이면 cashRegister에 20 넣고..? 20달러짜리 지폐가 있나? 5, 10 | 5, 5, 5 반환하고

        if(bill === 20) {
            const total = cashRegister.reduce((acc, cur) => acc + cur, 0);
            const checkCash = (cur) => cur === 10;
            
            if (total < 15)
                return false;
            if (total >= 15) {
                if (cashRegister.every(checkCash))
                    return false;
                else
                    //손님께 거스름돈 돌려주는 과정

                    //여길 어떻게..?

            }
                
            cashRegister.push(bill);
        }
    }
    return true;
};

 

다만, 이 코드의 문제는 cashRegister가 배열이여서 손님에게 거스름돈을 돌려줄때가 문제였다.

물론 백트래킹으로 하나하나 원소를 더했다 뺐다 하면서 합이 15$가 되는 걸 찾을 수 있겠지만, 그렇게되면 배열을 잘라내는 부분이 썩 번거로워진다.

 

잠시 고민하다가

 

cashRegister에 들어있는 지폐(5달러, 10달러)는 갯수가 중요한거지, 지폐가 들어온 순서는 중요한 건 아니니 아래와 같이 코드를 수정해주었다.

var lemonadeChange = function(bills) {
    let five = 0;
    let ten = 0;

    for (let bill of bills) {
        if (bill === 5)
            five++;
        if (bill === 10)    {
            if (five > 0) {
                five--;
                ten++;
            } else {
                return false;
            }
        }
        //20에서는 five가 무조건 1이상 있어야함
        if (bill === 20)    {
            if (five >= 3)  {
                five= five - 3;
            } else if (five > 0 && ten > 0)   {
                five--;
                ten--;
            } else {
                return false;
            }

        }
    }
    return true;
};

 

이러고 제출했을 때, 분명 맞았다고 생각했는데 wrong answer가 떠서 당황스러웠다.

 

 

???????????????

 

코드를 살짝 수정해서 콘솔로그를 다 찍어봤다가 깨달았다.

 

bill이 20일때 five가 3인것부터 체크해서 넘어가니 자연스레 1이 체크되지 않았던 것

 

작은 수부터 확인하고 넘어갔어야했는데, 큰 수부터 체크하고 가면 더 빨리 넘어갈거라는 내 안일한 생각이 그르쳤다.

 

 

최종 제출정답은

var lemonadeChange = function(bills) {
    let five = 0;
    let ten = 0;

    for (let bill of bills) {
        if (bill === 5)
            five++;
        if (bill === 10)    {
            if (five > 0) {
                five--;
                ten++;
            } else {
                return false;
            }
        }
        //20에서는 five가 무조건 1이상 있어야함
        if (bill === 20)    {
            if (five > 0 && ten > 0)  {
                five--;
                ten--;
            } else if (five >= 3)   {
                five = five - 3;
            } else {
                return false;
            }

        }
    }
    return true;
};

 

오늘은 무사히 클리어!