문제 68. 햄버거 만들기 (난이도 7)

 

 

function solution(ingredient) 
{
    let humburger = '1231'
    let makeHumburger = ''
    let answer = 0;
    for(let i = 0; i < ingredient.length; i++)
    {
        makeHumburger += ingredient[i]
        if(makeHumburger.includes(humburger))
        {
            makeHumburger = makeHumburger.split('').splice(0,makeHumburger.length-4)
            makeHumburger = makeHumburger.join('')
            //console.log(makeHumburger)
            answer++;
        }
    }
    console.log(makeHumburger)
    return answer;
}

 

같이 splice로 풀어봤지만, 시간초과가 떳다...

 

slice 등 다른 방법으로 코드를 작성 했을 때에도

 

또!!! 시간초과가 떳다...

 

며칠을 생각해보다가, stack을 사용해서 알고리즘을 작성하니

 

시간초과가 뜨지 않았다...

 

아무래도 문자열을 조작하는 방식은

해당 문자에 접근해야하기 하기 때문에

O(n)의 시간이 걸리게 되는데,

 

stack을 사용해서 데이터를 빼는 과정은

stack의 맨 위 데이터만 빼면 되기 때문에

O(1)의 시간이 걸려서 시간초과를 피할 수 있었던 것 같다...

 

제출한 코드 : 

 

function solution(ingredient) 
{
    let count = 0
    let stack = []
    // 입력 받은 문자 저장할 배열
    for(let i = 0; i < ingredient.length;i++)
    {
        stack.push(ingredient[i])
        // 문자 저장
        if(stack.length >= 4)
        {
               const makeBurger = stack.slice(-4).join('')
               // 이전 4개 값이 
               if(makeBurger === '1231') //1231이면
               {
                   stack.pop()
                   stack.pop()
                   stack.pop()
                   stack.pop()
                   //1231 제거
                   count++;
                   //개수 증가
               }
        }
    }
    return count
}