Algorithm 11장 - 박스포장

Algorithm

박스포장

문제

• 마트에서 장을 보고 박스를 포장하려고 합니다.

• 박스를 포장하는 데는 폭이 너무 좁습니다. 그렇기에 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다.

• 불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다.

• 뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 합니다. 앞사람이 포장을 끝내면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다.

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

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

입력

• 인자 1 : boxes
  • Number 타입을 요소로 갖는, 포장해야 하는 박스가 담긴 배열
    • 1 ≤ 사람 수 ≤ 10,000
    • 1 ≤ 박스 ≤ 10,000

출력

• Number 타입을 리턴해야 합니다.

주의 사항

• 먼저 포장을 전부 끝낸 사람이 있더라도, 앞사람이 포장을 끝내지 않았다면 나갈 수 없습니다.

예시

• 만약 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
  
  const boxes2 = [1, 5, 7, 9];
  const output2 = paveBox(boxes2);
  console.log(output2); // 1
  

코드

function paveBox(boxes) {}

코드 설명

function paveBox(boxes) {
  let box = boxes[0];
  let max = 1;
  let count = 1;

  for (let i = 1; i < boxes.length; i++) {
    boxes[i] <= box ? count++ : ((count = 1), (box = boxes[i]));
    max < count && (max = count);
  }

  return max;
}

코드 설명

• let box = boxes[0]
  • 입력받은 배열의 첫 번째 요소를 box에 담는다.
  • 첫 번째 박스 크기에 따라, 뒤에 정렬돼 있는 박스들 중 몇 개나 동시 작업이 가능한지 판별하기 위해서이다.
• let max = 1
• let count = 1
  • 박스가 동시에 처리될 수 있는 갯수를 비교해주기 위해 선언한다.
• for(...){...}
  • boxes[i] <= box ? count++ : (count = 1, box = boxes[i])
    • 배열의 첫 번째 요소가 다른 요소들보다 크다는 것은 동시에 작업할 수 있다는 뜻이기 때문에 최대 동시작업 갯수를 나타내는 count에 1씩 더해준다.
    • 만약 작다면, 다시 새로운 요소를 기준으로 작업을 시작해야되기 때문에 box에는 더 큰 요소를 재할당하고 count는 1로 만든다.
  • max < count && (max = count)
    • 만약 동시에 작업할 수 있는 최대 숫자보다, 현재 동시 작업 갯수가 더 클 경우 최대 작업 갯수는 count로 재할당된다.