Queue 문제는 제대로 풀지 못해서 실패한 코드와 왜 실패했는지, 레퍼런스 코드는 어떤 방식으로 풀었는지 정리했습니다.🚀


문제

만약, 앞사람의 박스는 5 개고, 뒷사람 1의 박스는 4 개, 뒷사람 2의 박스는 8 개라고 가정했을 때, 뒷사람 1이 제일 먼저 박스 포장을 끝내게 되어도 앞사람 1의 포장이 마칠 때까지 기다렸다가 같이 나가게 됩니다.

이때, 통틀어 최대 몇 명이 한꺼번에 나가는지 알 수 있도록 함수를 구현해 주세요.

예시

1
2
3
4
5
6
7
const boxes = [5, 1, 4, 6];
const output = paveBox(boxes);
console.log(output); // 3

const boxes2 = [1, 5, 7, 9];
const output2 = paveBox(boxes2);
console.log(output2); // 1

실패 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function paveBox(boxes) {
  let count = 0;
  let test = [];

  while (true) {
    if (boxes[0] === 0) break;
    boxes = boxes.map((box) => (box === 0 ? 0 : box - 1));
  }

  for (let i = 0; i < boxes.length; i++) {
    if (boxes[i] === 0) count += 1;
    if (boxes[i + 1] !== 0) return count;
  }
}

🫥 무엇이 잘못되었을까?

처음 문제를 봤을 때 첫 번째 사람이 작업을 끝냈을 때 즉, boxes[0]이 0일 때, 뒤에 연속으로 0인 요소의 갯수를 세면 되지 않을까?라는 아이디어를 가지고 문제를 풀었습니다.

하지만 이 아이디어에 오류가 있었는데요, 첫 번째로 한꺼번에 나간 뒤에 상황을 고려하지 않았다는 겁니다. 제 코드는 0번째 사람이 작업을 끝내고 나서 한꺼번에 나간 사람의 수만 리턴하고 있기 때문이죠

그럼 어떻게 풀어야할까요?


Reference 코드

Reference Code의 Pseudo code는 다음과 같습니다.

  • 최대 나간 사람의 수를 담을 수 있는 배열(answer)를 선언한다.
  • while문 👉🏻 boxes 배열이 0보다 클 때가지 반복한다.
    • findIndex 메서드를 사용해서 boxes[0]번째보다 큰 수가 존재하기 전까지의 index를 구한다.
    • 만약 findIndex가 -1이라면?
      • boxes[0]번째가 가장 크다는 의미
      • answer에 boxes.length를 넣고 boxes를 빈 배열로 초기화한다.
    • findIndex가 존재한다면?
      • 해당 인덱스를 answer에 넣고 boxes에서 그만큼을 제외한다.
  • answer에 존재하는 값 중 가장 큰 값을 반환한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function paveBox(boxes) {
  let answer = [];

  // boxes 배열이 0보다 클 때까지 반복합니다.
  while (boxes.length > 0) {
    let finishIndex = boxes.findIndex((fn) => boxes[0] < fn);

    if (finishIndex === -1) {
      // 만약 찾지 못했다면 answer에 boxes 배열의 길이를 넣은 후, boxes 내부의 요소를 전부 삭제합니다.
      answer.push(boxes.length);
      boxes.splice(0, boxes.length);
    } else {
      // 만약 찾았다면, 해당 인덱스를 answer에 넣고, boxes에서 그만큼 제외합니다.
      answer.push(finishIndex);
      boxes.splice(0, finishIndex);
    }
  }

  // 결과물을 반환합니다.
  return Math.max(...answer);
}

다른 사람의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function paveBox(boxes) {
  const queue = [];
  let count = 0;
  let standard = boxes[0];

  for (let i = 0; i < boxes.length; i++) {
    if (boxes[i] <= standard) {
      count += 1;
    } else {
      queue.push(count);
      standard = boxes[i];
      count = 1;
    }
  }
  queue.push(count);

  return Math.max(...queue);
}

👉🏻 배열을 건드리지 않아도 되는 간단한 코드를 만들 수도 있구나!라는 생각을 하게되었습니다. 다른 사람의 코드를 보는 게 굉장한 도움이 되는 것 같습니다:)
(알려주신 즨솔님께 감사를 표하며,,,)