Github

햄버거 만들기

1. 개요

2. 문제 설명

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

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

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

2-1. 문제 설명 - 제한사항

  • 1 ≤ ingredient의 길이 ≤ 1,000,000

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

2-2. 문제 설명 - 입출력 예

ingredient
result

[2, 1, 1, 2, 3, 1, 2, 3, 1]

2

[1, 3, 2, 1, 2, 1, 3, 1, 2]

0

2-3. 문제 설명 - 입출력 예 설명

입출력 예 #1

  • 문제 예시와 같습니다.

입출력 예 #2

  • 상수가 포장할 수 있는 햄버거가 없습니다.

3. 문제 풀이

function solution(ingredient) {
  // 1) 만든 햄버거의 개수를 세는 변수 만들기
  let count = 0;

  // 2) 요소가 1인 인덱스부터 시작하기
  let i = ingredient.indexOf(1);
  while (i < ingredient.length) {
    if (canMake(i)) {
      // 4) 현재 인덱스부터 4개의 요소를 제거하기
      ingredient.splice(i, 4);

      // 5) 만든 햄버거의 개수를 1더하고 시작 인덱스를 2만큼 감소시키기
      count += 1;
      i -= 2;
      continue;
    }
    i += 1;
  }

  // 3) 햄버거가 만들어질 수 있는지 확인하는 함수
  function canMake(i) {
    return (
      ingredient[i] === 1 &&
      ingredient[i + 1] === 2 &&
      ingredient[i + 2] === 3 &&
      ingredient[i + 3] === 1
    );
  }

  return count;
}

1) 만든 햄버거의 개수를 세는 변수 만들기

let count = 0;

count 변수는 반복문에서 햄버거가 만들어 질 수 있는 조건일 때 1씩 증가된다. 이는 이후에 반환되는 값이다.

2) 요소가 1인 인덱스부터 시작하기

let i = ingredient.indexOf(1);

반복문은 i가 ingredient 배열의 길이보다 커지기 전까지 실행된다. 하지만 만약 요소가 1(빵)이 아닌 다른 요소로 시작하면 햄버거는 만들어질 수 없으므로 처음으로 1이 나타나는 인덱스부터 반복문을 시작한다.

3) 햄버거가 만들어질 수 있는지 확인하는 함수

function canMake(i) {
  return (
    ingredient[i] === 1 &&
    ingredient[i + 1] === 2 &&
    ingredient[i + 2] === 3 &&
    ingredient[i + 3] === 1
  );
}

매 반복문에서 canMake 함수가 실행된다. 해당 함수는 현재의 i를 받아서 자신과 이후 3개의 요소를 확인하여 햄버거가 만들어 질 수 있는 조건이 되는지 boolean 타입을 반환한다.

4) 현재 인덱스부터 4개의 요소를 제거하기

ingredient.splice(i, 4);

만약 햄버거가 만들어진다면 ingredient 배열의 i번째 부터 4개의 요소를 제거해야 한다.

5) 만든 햄버거의 개수를 1더하고 시작 인덱스를 2만큼 감소시키기

count += 1;
i -= 2;
continue;

햄버거가 만들어졌으니 count를 1증가시킨다.

i는 2를 감소시키는데 이는 아래와 같은 경우를 살펴보며 이유를 알아보자.

  • [1, 1, 1, 2, 3, 1, 2, 3, 1, 2]

위와 같은 배열에서 첫 번째 햄버거는 2번 인덱스에서 만들어진다. 만들어진 이후의 배열의 모습은 아래와 같다.

  • [1, 1, _, _, _, _, 2, 3, 1, 2] -> [1, 1, 2, 3, 1, 2]

이때 현재 i는 2이기 때문에 다음 반복문에서는 세 번째 요소 부터 햄버거가 만들어 질 수 있는지 확인할 것이다. 이렇게 된다면 더 이상 만들 수 있는 햄버거는 없다. 하지만 정말로 그럴까? 바로 위의 배열에서 1번 인덱스부터 하나의 햄버거가 만들어 질 수 있다. 이를 생각해야하기 때문에 2를 감소시키는 것이다. 또 다른 예시를 표를 통해 알아보자.

반복 횟수
ingredient
i
count

0

[1, 1, 1, 2, 1, 2, 3, 1, 3, 1, 2]

0

0

1

[1, 1, 1, 2, 1, 2, 3, 1, 3, 1, 2]

0

0

2

[1, 1, 1, 2, 1, 2, 3, 1, 3, 1, 2]

1

0

3

[1, 1, 1, 2, 1, 2, 3, 1, 3, 1, 2]

2

0

4

[1, 1, 1, 2, 1, 2, 3, 1, 3, 1, 2]

3

0

5

[1, 1, 1, 2, 3, 1, 2]

4

0

6

[1, 1, 2]

2

0

7

[1, 1, 2]

0

0

8

[1, 1, 2]

1

0

9

[1, 1, 2]

2

0

다시 정리하다면 이미 지나간 재료들 중에서도 중간에 햄버거가 만들어졌다면 이후의 재료들과 순서가 맞을 수 있기 때문이다.

해당 부분을 간과하고 재귀로만 풀려고 했기 때문에 계속 오류가 났었다.

결과

4. 다른 사람의 풀이

스택으로 푼 문제가 인상이 깊어 해당 문제를 가져왔다.

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

스택을 사용한다는 것은 햄버거의 재료 순서를 반대로 한다는 것과 마찬가지이다. 하지만 이는 상관이 없는 문제이기 때문에 오히려 더욱 좋은 해결책이 될 수 있다고 생각한다.

매 반복문에서 ingredient 요소를 stack에 넣는다. 이후 마지막 요소부터 4개의 요소를 탐색하여 햄버거가 만들어 질 수 있는 조건이라면 count를 1증가키기고 뒤에서부터 4개의 요소를 제거한다.

끝이다. 간단해 보이지만 이러한 해결법을 찾는것은 아직 어려울 것이다. 너무 일관적으로 생각만해서 그런거같다. 순서를 바꿔 생각해보는 것도 의식적으로 연습해보자.

결과

오래걸렸던 몇몇의 문제의 실생 속도가 줄어든 것이 눈에 띄게 보인다.

5. Conclusion

오랜만은 1시간 이상 걸리는 문제였다. 앞으로 레벨2로 올라가게 된다면 이보다 더 어렵고 시간이 오래 걸리는 문제들을 마주하게 될 텐데 내가 잘 해결해 나갈 수 있을까하는 걱정이 든다. 시간이 충분하고 다른 공부를 하지 않아도 된다면 하나의 문제를 가지고 하루종일 붙자고 있는 것도 좋지만 그렇지 않아서 고민이 많다. 어느정도까지 스스로 고민하고 해결하는 것이 좋은지 조언을 구해봐야겠다. 스스로 성장했다고 느낀 점은 의식적으로 시간복잡도가 O(n^2)가 되지 않도록 코드를 구현했다는 것이다. 물론 제한사항에 있는 배열의 길이에 따라 달라질 수 있겠지만 최대한 O(logn) 또는 O(n)이 되도록 하자.

📅 2022-01-14

Previous숫자 짝꿍Next둘만의 암호

Last updated