[프로그래머스/JS] LEVEL1 햄버거 만들기

[문제]

[오답코드]

function solution(ingredient) {
    var answer = 0;
    ingredient = ingredient.join("");
    const pos = '1231';
    let num = 0;
    let count = 0;
    while(1){
        let num = ingredient.indexOf(pos);
        if(num != -1){
            count++;
            ingredient = ingredient.replace(pos, '');
        }
        else{
            break;
        }
    }
    
    return count;
}

처음에는 ingredient에서 겹치는 '1231'을 찾아서 찾게되면 해당하는 구간을 replace로 지우고 해당구간을 공백으로 바꾸게끔 하는 코드를 구상하였다. 하지만 시간초과가 나서 잘 실행되지 않았다. 그래서 이유를 생각했을 때 계속 indexOf로 최대 100만개의 예시를 찾으니깐 많이 느려졌던 것 같다. 이거를 while문으로 반복하니깐 그럴 수 있다고 생각하게 되었다.

[풀이코드]

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;
}

[해설]

그래서 스택의 개념을 이용하였다. 스택으로 재료들을 하나씩 담고 스택이 4개이상 되었을 경우 해당 스택을 잘라내서 '1231' 맞는지 확인하고 맞다면 스택의 -4부분 뒤에서 4개를 다 자르고 앞의 부분만 남기고 answer의 값을 하나 올려주는 것으로 문제를 해결하였다. 이렇게하면 한번만 100만개의 코드를 확인하면되어서 시간복잡도가 많이 줄어들게 된다.