Programmers Algorithm - 햄버거 문제

햄버거는 빵, 고기, 야채, 빵 순으로 만들 수 있고 이는 각각 1, 2, 3, 1 로 표현할 수 있다. 1, 2, 3 으로 이뤄진 배열을 arguments 로 줄 때, 몇 개의 햄버를 만들 수 있는 지에 대한 문제다.

문자열로 풀기

처음에는 단순하게 문자열로 처리하려고 했다.

function test1(ingredient) {
    let joinedIngredient = ingredient.join('');
    let count = 0;
    
    while(true) {
        const reducedIngredient = joinedIngredient.replace('1231', '');
        if(joinedIngredient === reducedIngredient) {
            break;
        }
        count++;
        joinedIngredient = reducedIngredient;
    }
    return count;
}

시간복잡도를 생각해보면 처음 Arrray.prototype.join() 은 O(n) 이 걸린다.
String.prototype.replace() 는 O(m) 으로 m 은 joinedIngredient 의 길이다. 추가로 while 문에서 replace 가 도는 최악의 경우는 m / 4 이기에 O(n^2) 시간이 걸릴 수 있다.
최악의 경우 O(n) + O(m^2) 시간이 걸리고 평균 O(n) + O(mk) 시간이 나올 수 있다.

조건에 n 은 1,000,000 까지 나올 수 있는데 실행결과 결국 시간초과가 발생했다.

배열로 풀기 (feat. Array.prototype.splice)

문자열로는 한계가 있어보여서 배열 그 자체로 풀어보려고 했다.

function test2(ingredients) {
    let count = 0;
    let findFirstIngredientIndex = -1;
    do {
        findFirstIngredientIndex = ingredients.findIndex((ingredient, index) => {
            const isFirstOne = ingredients[index] === 1;
            const isSecondTwo = ingredients[index + 1] === 2;
            const isThirdThree = ingredients[index + 2] === 3;
            const isLastOne = ingredients[index + 3] === 1;
            
            return isFirstOne && isSecondTwo && isThirdThree && isLastOne;
        });   
        if(findFirstIngredientIndex !== -1) {
            ingredients.splice(findFirstIngredientIndex, 4);
            count++;            
        }
    } while(findFirstIngredientIndex !== -1)
    return count;
}

do-while 문에서 findIndex 는 O(n) 시간이 걸리고 splice 도 O(n) 시간이 걸리기에 결국 O(n^2) 시간 복잡도를 가지는 로직이다.

역시나 제출 시, 시간 초과를 하게 되었다.

배열로 풀기 (feat. Array.prototype.pop)

회사 동료가 stack 으로 풀어보라는 조언을 줘서 다시 로직을 작성해봤다.

function solution(ingredients) {
    let count = 0;
    const ingredientStack = [];
    ingredients.forEach((ingredient) => {
        ingredientStack.push(ingredient);
        if(ingredientStack.length >= 4) {
            if(
                ingredientStack[ingredientStack.length - 1] === 1 &&
                ingredientStack[ingredientStack.length - 2] === 3 &&
                ingredientStack[ingredientStack.length - 3] === 2 &&
                ingredientStack[ingredientStack.length - 4] === 1
            ) {
                count++;
                ingredientStack.pop();
                ingredientStack.pop();
                ingredientStack.pop();
                ingredientStack.pop();
            }
        }
    });
    return count;
}

ingredients.forEach 가 O(n)
각각의 condition check logic 도 O(1)
ingredientStack.push 는 O(1)
ingredientStack.pop 는 O(1)
O(n) * O(1) = O(n)

이를 제출했을 때 덕분에 통과할 수 있었다.

최종

stack 으로 풀어야겠다는 생각을 전혀 하지 못했고 stack 을 쓰지 않았을 때 시간 복잡도가 이렇게 차이가 날 수도 있다는 사실을 알게 된 좋은 문제였다.

순회할 때 순서와 삭제의 순서가 모두 고려되어야 하는 경우 stack 을 고려해보자.