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

https://school.programmers.co.kr/learn/courses/30/lessons/133502

프로그래머스

 

 

목차

• 문제
• 풀이
• 코드

문제

입력

ingredient (배열) - 햄버거 재료 배열.

 

출력

result (숫자) - 상수가 1, 2, 3, 1 순서로 햄버거를 만든 횟수

 

제한사항

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

풀이

먼저 이 문제를 읽자마자 스택이 생각났다. 왜 스택이냐구? 먼저 햄버거를 만드는 순서 1, 2, 3, 1을 꼭 지켜야 하고 이 조건을 만들었을 경우 햄버거를 만들 수 있다, 곧 1, 2, 3, 1을 배열에서 pop() 하기 때문이다. (참고로 스택은 선입후출, FILO이다.) 시간 복잡도는 최소가 O(kn) (k는 상수)가 되겠다. 왜냐하면 모든 배열을 한 번씩 순회해야 최소로 1, 2, 3, 1이 순서를 확인할 수 있고 이 과정에서 조건문은 반드시 필요하기 때문이다.

 

이를 바탕으로 햄버거가 될 수 있는 후보를 담은 배열과 횟수를 담을 변수를 선언하였다. 그리고 인덱스가 필요하지 않기 때문에 배열을 순회할 때 for...of을  활용하여 구현하였다. [1, 2, 3, 1]을 어떻게 검사할까 생각하다가 햄버거 후보 배열의 뒤에서부터 차례대로 검사하기로 결정했다. 이 때 좀 더 정확하게 검사하기 위해서 햄버거 후보 배열이 3 초과 즉 4 이상일 때 검사하도록 if 문을 만들었다. if 문의 조건을 충족할 때 splice문을 사용하여 마지막의 4 원소를 pop() 시키고 햄버거를 만든 횟수를 1 증가시켰다.

 

시간 복잡도는 조건문과 반복문 때문에 O(kn)(k는 상수)이다.

공간 복잡도는 ingredient의 배열의 크기인 O(n)이다.

코드

function solution(ingredient) {
    var answer = 0;
    const order = [];
    
    for (v of ingredient) {
        order.push(v);
        if (order.length > 3 && order.at(-4) === 1 && order.at(-3) === 2 && order.at(-2) === 3 && order.at(-1) === 1) {
            order.splice(-4, 4);
            answer++;
        }
    }
    
    return answer;
}

 

 

굳이 splice(-4, 4)라고 안쓰고 splice(-4)라고 써도 되었다. (어차피 다 4 원소 모두 지우기 때문에.)

또한 pop()을 4번 하는 것이 좀 더 스택의 특징에 맞는 코드이다.

다른 사람의 풀이는 order.at(-1)를 안 쓰고 order[order.length -1]을 쓴다. 참고하자.