[알고리즘 JS] 햄버거 만들기 (프로그래머스 Lv.1)

문제

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

프로그래머스

• 숫자 배열에서 1,2,3,1 의 연속된 수가 나올 수 있는 횟수를 구하여야함!

풀이(정답)

function solution(ingredient) {
  let count = 0;
  let stack = [];

  for (let item of ingredient) {
    stack.push(item);

    if (stack.length >= 4) {
      let burger = stack.slice(-4).join('');

      if (burger === '1231') {
        // stack = stack.slice(0, -4);
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        count++;
      }
    }
  }
  return count;
}

• ingredient 배열을 돌며 길이가 4가 될 때까지 stack에 push 한다.
• 길이가 4이상이 되면 현재까지 쌓인 재료를 문자열로 변경하고 1231이 되는지 확인한다.
• 1231이 되는 경우 스택의 재료를 삭제하고 카운트를 올린다.
• 다음 반복부터는 연속된 1231이 없어지고 그 다음 재료부터 스택에 쌓인다.
• 처음에 삭제하는 부분을 slice로 구현했더니, 전체 배열을 다시 탐색해야되서 그런지? 시간초과 오류가 떴다. 그래서 별도의 탐색을 거치지 않고 가장 마지막 요소를 제거하는 pop을 4번;; 해줬다.

다른 분의 풀이

function ref(ingredient) {
  let count = 0;

  for (let i = 0; i < ingredient.length; i++) {
    // 현재 인덱스부터 4칸까지가 일치하는지 확인
    if (ingredient.slice(i, i + 4).join('') === '1231') {
      count++;
      // splice로 일치하는 부분을 삭제
      ingredient.splice(i, 4);
      // 인덱스를 다시 뒤로 돌려서 탐색 시작 **
      i -= 3;
    }
  }

  return count;
}

 

• 이 분은 스택을 사용하지 않고 index를 뒤로 돌리는 방법으로 푸셨다. 순차적으로만 진행되어야 하는 줄 알았는데 중간에 순서를 뒤로 가게 만들수도 있다는게 놀라웠다...!
• stack을 쌓지 않고 현재 인덱스부터 앞에 있는 4칸까지 재료가 1231이랑 일치하는 경우에 splice 메서드를 사용해 일치하는 부분을 삭제하였다. 위에 pop을 4번하여 삭제한 내 코드에 splice 메서드를 적용하여 제거하니 시간초과 오류 없이 잘 통과가 되었다.
• slice와 splice의 차이점 : slice 는 어떤 배열의 시작 ~ 끝까지 얕은 복사를 하여 새로운 배열을 만드는 것이고, splice는 기존의 요소를 삭제하거나 교체하는 메서드이다. 인자를 어떻게 전달하느냐에 따라서 비슷한 용법으로 사용할 수 있지만 새로운 배열을 만들어낸다는 점에서 주어진 배열의 길이가 길 때 더 오랜 시간이 소요되는 것으로 보인다.
• 같은 맥락에서 처음에는 재귀를 사용해서 풀었더니 시간초과가 떴음. 배열의 길이가 긴 경우에는 재귀처럼 어떤 배열을 다시 탐색해야하는 경우를 만들지 않는게 좋겠다.