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

문제 설명

 

문제 분석

• 햄버거 가게에서 일하는 상수는 정해진 순서(아래서부터 빵-야채-고기-빵)로 쌓인 햄버거를 포장해야 합니다.
• 재료가 순서대로 들어올 때마다 햄버거를 만들 수 있는지 확인하고, 만들 수 있다면 포장합니다.
• ingredient 배열에는 1(빵), 2(야채), 3(고기)의 값이 담겨있습니다.
• 상수가 포장할 수 있는 햄버거의 개수를 반환해야 합니다.

 

첫 번째 접근:  문자열 조작(O(n²) ) (시간 초과)

function solution(ingredient) {
    const hamburger = '1231'
    let answer = 0
    
    ingredient = ingredient.join('')
    
    while(ingredient.includes(hamburger)) {
        ingredient = ingredient.replace(hamburger, '')
        answer += 1
    }
    return answer
}

 

• 매번 전체 문자열에서 패턴을 검색하는 includes()와 호출할 때마다 새로운 문자열을 생성하는 replace()를 사용했습니다. 
• 긴 재료 목록에서 시간 복잡도가 O(n²)에 가까워지게 되며 해당 코드는 시간 초과를 야기합니다.

 

 

 

두 번째 접근: Stack (O(n))

function solution(ingredient) {
    const hamburger = '1231'
    let answer = 0
    
    return ingredient.reduce((a, c, i) => {
        a.str.push(c)
        if(a.str.slice(-4).join('') === hamburger) {
            a.str.splice(-4, 4)
            a.answer += 1
        }
        
        return a
    }, {answer: 0, str: []}).answer
}

개선 사항

• 전체 문자열을 매번 검사하지 않고, 최근 추가된 4개의 재료만 확인합니다.
• 불필요한 문자열 변환과 검색 작업을 제거했습니다.