❗ 문제 설명

❗ 제한사항

❗ 입출력 예

❗ 문제 요약

햄버거를 만들 때 빵-야채-고기-빵(1-2-3-1) 순으로 쌓인 햄버거만 포장할 수 있다.
상수가 포장할 수 있는 햄버거의 개수를 구하라

😂 실패 코드

function solution(ingredient) {
    let answer = 0;
    ingredient = ingredient.join("");
 
    while (ingredient.includes('1231')) {
        ingredient = ingredient.replaceAll('1231', '0')

        for (let i = 0; i < ingredient.length; i++) {
            if (ingredient[i] === "0") answer += 1;
        }
        
        ingredient = ingredient.replaceAll('0', '')

    }
    
    return answer;
}

위 코드로 풀면 통과하지 못하는 테스트 케이스가 생긴다.
[1, 2, 1, 2, 3, 1, 3, 1, 2, 3, 1, 2, 3, 1] 배열이 있다고 한다면
원래라면 앞에 1231이 없어져서 [1, 2, 3, 1, 2, 3, 1, 2, 3, 1] 되고
또 앞에서 1231이 없어져서 [2, 3, 1, 2, 3, 1] 되고
마지막 1231이 없어져서 [2, 3]이 되어 햄버거를 총 3번 만들 수 있게 된다.

그러나 위 코드로 풀게 되면 아마 1,2,3,1을 먼저 다 없애버리기 때문에
[1, 2, 0, 3, 0, 2, 3, 1]이 되어서 햄버거를 총 2번 밖에 만들지 못하게 된다.

function solution(ingredient) {
    let answer = 0;
    ingredient = ingredient.join("");
 
    while (ingredient.includes('1231')) {
         ingredient = ingredient.replace('1231', '');
        answer += 1;

    }
    
    return answer;
}

그래서 위 코드처럼 앞에서부터 하나씩 1231을 없애도록 구현을 해봤더니
이번엔 시간초과로 실패를 하게 된다.
아무래도 ingredient의 최대 길이가 1000000이기 때문에 while문안에서 문자열 탐색까지 들어가니 시간이 초과되는 것이라고 생각했다.

어떻게 풀까 생각하다가 문제의 예시 부분을 다시 읽고 이 문제는 스택써서 풀어야겠다는 생각이 들었다.
스택에 하나씩 재료를 추가하면서 스택에 들어있는 재료 4개의 값과 1231과 비교했을 때 같다면 없애주는 방식으로 풀면
재료의 for문을 한 번만 돌면서 앞에서부터 차례대로 햄버거를 포장할 수 있겠다고 생각했다.
(이전에 풀었던 크레인 인형뽑기의 bucket과 뽑은 인형을 비교하는 방법에서 착안한 방법이다.)

😎 정답 코드

function solution(ingredient) {
    let answer = 0;
    const stack = [];
    
    for (let i = 0; i < ingredient.length; i++) {
        stack.push(ingredient[i]);
        
        if (stack.length >= 4) {
            const burger_ingredient = stack.slice(-4).join("");
            
            if (burger_ingredient === '1231') {
                stack.splice(-4);
                answer += 1;
            }
        }
    }
    
    return answer;
}

위 코드처럼 stack배열에 하나씩 재료를 넣으면서 스택에 들어있는 재료 4개의 값과 1231과 비교 하는 방법을 사용하면 통과할 수 있다.

마무리하며

시간 초과가 떠서 당황을 조금 했지만 금방 해결책을 찾을 수 있었다.
요근래 stack 자료구조를 사용하는 문제를 좀 풀었더니 stack 자료구조와 좀 친근해진 기분이다.🤭