[programmers / JavaScript] 햄버거 만들기

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

// test
const ingredient = [2, 1, 1, 2, 3, 1, 2, 3, 1];

---

sol 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 hamburger = stack.slice(-4).join("");
      if (hamburger === "1231") {
        console.log(hamburger);
        stack.splice(-4, 4);
        count++;
      }
    }
  }

  return count;
}

스택을 하나 만들고 배열을 하나씩 담다가 1231 이 완성되면 카운트하는 방식으로 해결했다. 테스트 케이스처럼 중간에 1231을 빼고 난 후 그 자리의 앞뒤의 조합으로 다시 1231이 만들어지는지 알아야 하는데, 원본 배열 안에서 이를 해결하려 하면 속도가 느려질 수 있다( 여태 지나온 배열을 처음부터 다시 탐색하기 때문 ) 그래서 이런 문제는 스택을 만들어 여기서 조건을 만족하는지 찾는 것이 좋다.

 

sol 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문이 도는 와중에 i -= 3 처럼 인덱스를 조절하여 뒤로 가는 게 가능하다는 걸 알았다. (충격) 다만 sol 1에 언급한 것처럼 splice를 사용해 배열을 자르면서 원본  배열을 처음부터 다시 탐색하기 때문에 메모리와 시간을 많이 사용한다.

 

번외로 배열이

const ingredient = [1, 2, 3, 1, 2, 3, 1, 1];

인 경우 앞에서부터 1231 을 탐색했다면 햄버거는 하나 밖에 못 만들지만 중간의 1231을 먼저 잘라내면 앞뒤의 조합으로 햄버거를 총 2개 만들 수 있다. 즉 주어진 배열에서 최대로 만들 수 있는 햄버거 개수를 물었다면 이런 케이스까지 처리해야 했지만 이번 문제는 배열의 앞에서부터 탐색한다는 조건이 붙어있기 때문에 고려할 필요는 없다. 문제를 잘 읽자