[Programmers] 햄버거 만들기 (JS)

 

처음에 문제를 봤을 땐 stack이 바로 떠오르지 않았다.

ingredient의 길이가 1백만 이기에, 만일 for문을 2번 돈다 해도, 시간초과의 늪에 걸릴줄 몰랐다..

 

잘못된 문제 해결을 먼저 보자.

// 잘못된 접근

let str = ingredient.join('');

while(str.indexOf('1231') !== -1){
	if(str.indexOf('1231') !== -1){
    	answer++;
        str.replace('1231', '')
    }
 }
 ...

 

이렇게 되면 만약 최악의 경우를 생각해본다면 n^2의 시간복잡도가 나올 수 있었을 것 같다.

사실 이걸 알았음에도 불구하고 1백만이라는 너무 약하게 본것도 있다.

 

다시 돌아와 배열을 이용한 stack 의 풀이 방식을 작성했다.

 

방식은 배열에 한개씩 집어넣으면서, 배열속 마지막 4개가 1231을 만들 수 있는지 확인하여, 만들 수 있다면 배열에서 다시 제거하는 방법이다. 이는 n의 시간복잡도를 갖는다.

 

// 올바른 풀이
function solution(ingredient) {
    var answer = 0;
    let stack = [];
    
    for(let i=0; i<ingredient.length; i++){
        stack.push(ingredient[i]);
        if(stack.slice(-4).join('') === '1231'){
            answer++;
            stack.splice(-4);
        }
    }

    return answer;
}