[프로그래머스 - JS] level.1 햄버거 만들기 ❗️실수

 

프로그래머스

 

---

나의 풀이 

 

시간 복잡도 계산이랑 설계를 잘 못했다.

그리고 문제이해를 잘 못했다. 

상수의 앞에 아래서부터 위로 쌓이게 된다!! 

정해신 순서로 쌓인 햄버거만 포장을 한다!!

 

즉 재료가 빵야채빵고기빵 이렇게 쌓이면 햄버거를 만들지 못한다.  

 

실수 포인트 1

나는 배열중에서 순서만 맞으면 중간에 무엇이 있어도 상관 안 했다.  

 

실수 포인트 2

여기서 2중 for문을 쓰면 안되는데 썼다 why?  문제이해를 똑바로 못해서 

이걸 쌓이는 도중에 햄버거를 만들어야하는데 다 쌓고 햄버거를 만들려고 해서 코드 설계 자체가 틀렸다. 

 

실수 포인트 3

arr.slice() 이든 arr.reverse() 이든 모두 시간복잡도가 O(n)이다. 따라서 for문 안에서 쓰면 시간 복잡도가 더 올라간다.

stack = stack.slice(0, stack.length-4)는 최악이다.    

뒤에 일부 배열만 제거하려면 시간 복잡도가 O(1)인 arr.pop() 또는 arr.splice(-4)가 더 좋다  

 

틀린 코드

function solution(ingredient) {
    
    let result = 0
    let stack = []
    
    for(let i = 0; i<ingredient.length; i++) {
        stack.push(ingredient[i])
        if(checkMeterial(stack)){
            stack = stack.slice(0, stack.length-4)
            result += 1
        }
    }
    return result
        
}

function checkMeterial(stack) {
    const order = [1,3,2,1]
    const rStack = [...stack].reverse()
    return order.every((number,index) => number === rStack[index])
}

 

 

정답 코드

function solution(ingredient) {   
    let result = 0
    let stack = []
    
    for(let i = 0; i<ingredient.length; i++) {
        stack.push(ingredient[i])
        if(canMakeHamburger(stack)){
            stack.pop()
            stack.pop()
            stack.pop()
            stack.pop()
            result += 1
        }
    }
    return result
}

function canMakeHamburger(stack){
    const firstBread = stack.at(-4) === 1
    const vegetable = stack.at(-3) === 2
    const meat = stack.at(-2) === 3
    const lastBread = stack.at(-1) === 1
    return  firstBread && vegetable  && meat && lastBread
}

---

 

다른 사람 코드

 

풀이 1

function solution(ingredient) {
    let stk = [];
    let count = 0;
    for (let i = 0; i < ingredient.length; i++) {
        stk.push(ingredient[i]);
        if (
            stk[stk.length-1] === 1 &&
            stk[stk.length-2] === 3 &&
            stk[stk.length-3] === 2 &&
            stk[stk.length-4] === 1
        ) {
            count++;
            stk.splice(-4);
        }
    }
    return count;
}

나도 pop 4번사용하는 거 말고 splice(-4)를 사용했으면 더 좋았을 것 같다.  

 

풀이 2

function solution(ingredient) {
    let count = 0;

    for (let i = 0; i < ingredient.length; i++) {
        if (ingredient.slice(i, i + 4).join('') === '1231') {
            count++;
            ingredient.splice(i, 4);
            i -= 3;
        }
    }

    return count;
}

와 이건 정말 생각지도 못했다. 

for문을 다시 되돌리는 생각도 하구나