햄버거 만들기

문제

풀이

처음 이 문제를 보고 생각한 방법은 배열을 합쳐서 문자열로 만들고 1231이 적힌 부분이 있다면 replace를 통해 교체하는 것 이었다.

function solution(ingredient) {
    var answer = 0;
    
    //ingredient 문자열로 합치기
    ingredient = ingredient.join('')
    //만들 수 있는 버거가 있다면 반복
    while(ingredient.includes('1231')){
        ingredient = mkBugger(ingredient)
        answer++
    }
    return answer;
}

//버거 하나 만들기
const mkBugger = ingredient => ingredient.replace(/1231/,'')

깔끔하게 끝날거라 생각했는데... 시간 초과로 오답이 나왔다.

왜 틀렸을까? 내가 생각한 이유는 두가지였다.

1.조건식에서 includes를 통해 한번 mkBugger의 replace를 통해 한번 동작하면서 비효율적인 시간복잡도를 가지게 됐다.

2.includes 자체가 문자열을 처음부터 끝까지 탐색하는 알고리즘을 가지고 있을 것이라 비효율적인 O(n)의 시간 복잡도를 가져서 문제가 생겼다.

어느쪽이건 includes에 문제가 있을거라 생각해 includes를 제거하고 더이상 교체할게 없으면 break를 쓰는 방법을 쓰기로 했다.

function solution(ingredient) {
    var answer = 0;
    
    //ingredient 문자열로 합치기
    ingredient = ingredient.join('')
    //만들 수 있는 버거가 있다면 반복
    while(1){
        var tmp = mkBugger(ingredient)
        if(tmp == ingredient) break;
        ingredient = tmp;
        answer++
    }
    return answer;
}

//버거 하나 만들기
const mkBugger = ingredient => ingredient.replace(/1231/,'')

tmp와 ingredient가 같은지 확인하여 교체된게 없다면 break를 통해 나오도록 했다. 돌려보니 사용된 시간이 절반가량 줄어들긴 했으나 여전히 오래걸렸고 시간초과로 인한 실패도 나왔다.

이쯤되니 replace에도 문제가 있음을 알았다. replace 또한 실행할때마다 처음부터 문자열을 다시 읽으니 비효율적으로 돌아가고 있었을 것이다.

해결방법을 고민하다보니 생각보다 간단한 방법이 떠올랐다. 배열을 stack의 구조로 구현하여 실시간으로 넣고 빼는걸 진행하면 O(1)의 방법으로 해결할 수 있을 것 같았다.

function solution(ingredient) {
    var answer = 0;
    var stack = [];
    
    
    for(var i=0 ; i<ingredient.length ; i++){
        //stack에 현재 인덱스의 재료를 넣음
        stack.push(ingredient[i])
        
        //버거가 만들어졌다면 stack에서 버거 제거
        if(stack[stack.length-4]==1
          && stack[stack.length-3]==2
          && stack[stack.length-2]==3
          && stack[stack.length-1]==1){
            stack.splice(stack.length-4,4)
            answer++
        }
    }
    return answer;
}

이렇게 stack구조를 채택하니 코드도 간결하고 시간도 굉장히 빠르게 문제가 해결됐다.