Javascript # 알고리즘 [Queue]

📝오늘 배운 내용

오늘은 알고리즘 문제를 풀 때 유용하게 사용할 수 있는 자료구조 중에서 큐(Queue)라는 것에 대해 알아보자.
큐(Queue)는 줄을 서서 기다리다, 대기행렬 이라는 뜻을 가지고 있다.
Stack과는 정반대로 먼저 들어간 데이터가 먼저 나오는(FIFO)형식을 특징으로 가지고 있다.
이러한 특성을 가진 큐를 사용해서 아래의 알고리즘 문제를 풀어보자.
예를 들어 우리가 마트에서 장을 보고 박스를 포장하려고 한다. 하지만 들어온 순서대로 한명씩 나갈 수 있다고 가정한다면 우리는 자료구조에서 큐를 떠올릴 수 있다.

예시는 아래와 같다.
boxes라는 배열에 [5, 1, 4, 6]이라는 값이 있을 때, 어떠한 함수를 실행하면 결과값으로 3이 출려된다.
이유는 5, 1, 4, 6이라는 배열이 왔을 때, 5개의 박스를 포장하는 동안 1, 4 개의 박스는 포장을 끝내고 기다리게 되고, 6 개의 박스는 포장이 진행 중이기 때문에, 5, 1, 4 세 개가 같이 나가고, 6이 따로 나가게 된다. 그렇기에 최대 3 명이 같이 나가게 된다.

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

이 문제의 정답은 아래와 같다.
우선 boxes배열이 빈 배열이 아닐 경우를 조건으로 주고 while문을 돌린다.
boxes의 첫 번째 요소와 나머지 요소들을 비교해서 첫 번째 요소보다 큰 값이 있는지 확인하기 위해
findIndex라는 메소드를 사용하여 boxes의 첫 번째 요소보다 더 큰 요소가 몇 번째 인덱스에 있는지 확인 한다.
첫 번째 요소는 5라고 생각하고, 만약 5보다 큰 값이 없다면, result라는 빈 배열에 boxes의 길이를 넣어준다. 반대로 5보다 큰 값을 찾았다면 그 값의 인덱스를 largerNum이라는 변수에 할당해준다. largerNum은 3이 될 것이고, 3이 정답이 된다.

function paveBox(boxes) { // [5, 1, 4, 6]
  let result = [];

  while (boxes.length > 0) {
    let largerNum = boxes.findIndex(el => boxes[0] < el); // largerNum = 3(6)
    if (largerNum === -1) {
      result.push(boxes.length); 
      boxes.splice(0, boxes.length);
    } else {
      result.push(largerNum);
      boxes.splice(0, largerNum);
    } 
  }
  return Math.max(...result);
}