[프로그래머스 / JS] Lv.1 햄버거 만들기

문제 설명

  햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수의 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 – 야채 – 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.

예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.

상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

---

제한사항

• 1 ≤ ingredient의 길이 ≤ 1,000,000
• ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

---

 

풀이

시간초과)

function solution(ingredient, numPackage = 0) {
    let lenOg = ingredient.length;
    
    ingredient = ingredient.join('');

    while (true) {
        if (ingredient === ingredient.replace('1231', '')) return (lenOg - ingredient.length) / 4   
        ingredient = ingredient.replace('1231', '')
    }
}

function solution(ingredient, numPackage = 0) {
    ingredient = ingredient.join('');
    
    let lenOg = ingredient.length;
    let idx = ingredient.indexOf('1231');
    
    while (idx != -1) {
        ingredient = ingredient.slice(0, idx) + ingredient.slice(idx + 4)
        idx = ingredient.indexOf('1231')
    }
    
    return (lenOg - ingredient.length) / 4
}

실행에 걸린 최대 시간 : 시간초과

 

개선 코드)

function solution(ingredient, numPackage = 0) {
    ingredient = ingredient.join('');
    
    let lenOg = ingredient.length;
    let idx = ingredient.indexOf('1231');
    
    while (idx != -1) {
        ingredient = ingredient.slice(0, idx) + ingredient.slice(idx + 4)
        idx = ingredient.indexOf('1231', idx - 3)
    }
    
    return (lenOg - ingredient.length) / 4
}

실행에 걸린 최대 시간 : 7283.89ms

사고과정

1. ingredient에서 '1231'의 문자열을 찾아 replace를 사용하면 되지 않을까?
2. while로 무한히 반복하고 replace로 갱신된 ingredient와 기존 ingredient을 비교해서 동일할 경우 포장을 다 한게 되니까 이 조건으로 while 문에서 탈출하면 되겠다.
3. 만들어진 햄버거 개수는 기존 ingredient의 길이와 최종적으로 갱신된 ingredient의 길이의 차를 4로 나눈것과 같다.
4. 시간초과!?
5. slice가 조금더 효율적이라는 소리가 있으니 slice를 써 볼까?
6. slice를 쓴다면 1231이 시작되는 인덱스를 알아야 하니까 indexOf를 써야겠네
7. 처음과 비슷하게 while문을 쓰고 조건을 indexOf의 결과값이 -1이 아닌 경우로 하자
8. while문 내에서 slice로 ingredient를 계속해서 갱신하고 idx또한 이에 맞추어 갱신해 indexOf = -1이 될때까지 돌려보자
9. 또 시간초과?!?!?
10.  아 indexOf를 사용할때 0 ~ idx - 4 까지는 이미 가능성이 없는 애들이니까 무시하면 그나마 개선되겠는데?
11. 오 성공!

평가

  열심히 노력한 흔적은 보이나 코드가 효율적이지 못하다....

 

개선점

  애초에 시작부터 잘못됐다. ingredient란 데이터의 집합을 덩어리로 볼게 아니라 차례대로 들어오는 데이터 값이라 보았으면 훨씬 효율적인 코드를 만들 수 있었을 것이다. 스택을 만들어 가장 앞쪽의 원소부터 받고, 매 원소를 받을 때 마다 -1 ~ -4 까지를 평가해 마치 테트리스처럼 조건에 제거하거나 유지하는 방식으로 코드를 짰으면 for문 한번으로 깔끔하게 끝났을 것이다.

 

스택 사용을 통한 개선)

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

 

위 코드와 같이 수정할 경우 실행 완료까지 걸리는 최대 시간이 44.62ms까지 단축된다.

알게된점

1. arr.at() 보다 arr[]가 빠르다
2. splice(-4)로 arr 뒷 부분을 자를 수 있다.