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

프로그래머스

 

 

✓ 풀이과정

function solution(ingredient) {
  let answer = 0;
  let findNewHamburder = true;

  while (findNewHamburder) {
    findNewHamburder = false;

    for (let i = 0; i < ingredient.length; i++) {
      const topping1 = ingredient[i];
      if (topping1 === 1) {
        let topping2 = ingredient[i + 1];
        let topping3 = ingredient[i + 2];
        let topping4 = ingredient[i + 3];
        let isHamburger = topping2 === 2 && topping3 === 3 && topping4 === 1;
        if (isHamburger) {
          answer++;
          ingredient = [
            ...ingredient.slice(0, i),
            ...ingredient.slice(i + 4, ingredient.length),
          ];
          findNewHamburder = true;
          break;
        }
      }
    }
  }

  return answer;
}

 

처음으로 접근했던 방식은 아래와 같습니다

 

1. ingredient 배열을 순회하며 햄버거의 첫 단계인 1을 발견하면 index, index+1, index+2, index+3 번째를 확인해서 햄버거 하나 [1, 2, 3, 1] 를 발견

2. 햄버거를 발견하면 완성된 햄버거 부분을 제외한 배열을 가지고 남아있는 재료를 모두 확인할 때까지 1번 과정을 반복

 

이렇게 채점해보면 일부 문제에서 시간초과가 발생하였고 중첩된 while/for문 매번 햄버거를 찾으면 배열을 제거하고 다시 반복하는 과정의 개선이 필요했습니다 → 시간초과 발생 개선 필요

 

 

✓ 최종코드

function solution(ingredient) {
  let answer = 0;
  let toppingStack = [];

  for (const element of ingredient) {
    let topping4 = element;
    toppingStack.push(topping4);

    let length = toppingStack.length;
    let topping1 = toppingStack[length - 4];
    let topping2 = toppingStack[length - 3];
    let topping3 = toppingStack[length - 2];

    let isHamburger =
      topping1 === 1 && topping2 === 2 && topping3 === 3 && topping4 === 1;

    if (isHamburger) {
      answer++;
      toppingStack.pop();
      toppingStack.pop();
      toppingStack.pop();
      toppingStack.pop();
    }
  }

  return answer;
}

 

해당 문제는 스택으로 보고 접근하면 훨씬 효율적인 방식으로 풀 수 있었습니다

 

재료가 쌓이는 구조라는 점을 생각해 봤을 때,  마지막에 쌓인 4개가 햄버거의 재료라면 마지막 4개만 제거하고 처음부터 순회할 필요없이 또 재료를 쌓으며 마지막 4개만 확인하는 과정을 반복하면 됩니다

 

1. 재료를 하나씩 쌓아갈 toppingStack 배열 선언

2. 재료를 하나씩 toppingStack에 추가하면서 마지막 4개의 재료가 햄버거의 구성이라면 마지막 4개를 toppingStack 배열에서 제거

3. 제공받은 모든 재료를 다 쌓을 때까지 2번을 반복

 

 

알고리즘 접근 방식을 고려하지 못해서 단순하게 기존 배열을 잘라내는 방법만 생각했는데,

저레벨 문제를 많이 풀어보면서 감을 익혀야 할 것 같습니다,,,!