[Queue] 박스 포장

박스 포장

문제

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

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

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

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

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

입력

인자 1 : boxes

• Number 타입을 요소로 갖는, 포장해야 하는 박스가 담긴 배열

출력

• 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

문제풀이

// 이 함수는 boxes 배열을 입력으로 받아 한 번에 나갈 수 있는 최대 인원수를 반환합니다.
function paveBox(boxes) {
  // 변수 초기화
  let front = ''; // 큐의 가장 최근 값
  let rear = ''; // 한 번에 나갈 값
  let count = 0; // 한 번에 나가는 인원 수
  let result = []; // 각 출구에서 나간 인원 수를 저장하는 배열

  // 큐에서 각 값을 검사합니다.
  while(boxes.length > 0){
    // 아무도 나가지 않는 경우, 다음 사람을 한 번에 나갈 값으로 지정합니다.
    if(count === 0){
      rear = boxes.shift();
      front = boxes[0];
      count++;
    }
    // 다음 사람이 현재 그룹과 함께 나갈 수 있는 경우, 인원수를 더합니다.
    else if(rear >= front){
      boxes.shift();
      front = boxes[0];
      count++;
      // 더 이상 사람이 없는 경우, 현재 인원수를 저장하고 반복을 종료합니다.
      if(boxes.length === 0){
        result.push(count);
        break;
      }
    }
    // 다음 사람이 현재 그룹과 함께 나갈 수 없는 경우, 현재 인원수를 저장하고 다시 세기 시작합니다.
    else{
      result.push(count);
      count = 0;
    }
  }
  // 한 번에 나간 인원 수 중 가장 큰 값을 반환합니다.
  return Math.max(...result);
}

위의 방식으로 작성했더니 테스트코드 하나가 통과하지 않는다

한 번에 나갈 수 있는 인원 중, 최대 인원을 리턴해야 합니다 (2)

Test Result

AssertionError: expected -Infinity to equal 1
    at Context.<anonymous> (/submission/index.test.js:77:29)
    at processImmediate (internal/timers.js:464:21) ... 

Test Code

() => {
    const result = range(10000, 44);
    expect(paveBox(result)).to.equal(9957);

    const result2 = range(10000, 8999);
    expect(paveBox(result2)).to.equal(1002);

    expect(paveBox([1])).to.equal(1);
  }

아래의 코드로 다시 작성해보았다 수정된 코드에서 배열의 첫 번째 상자는 firstBox의 초기 값하고 배열을 순회하고 firstBox의 값이 현재 상자의 값보다 크거나 같은지 확인시킨다. 만약 첫번쨰 박스보다 작은경우 한 번에 나갈 수 있는 상자의 수가 증가시킨다. 그렇지 않은 경우 현재 최대 카운트와 비교하여 더 크면 최대 카운트를 업데이트한다. 그러면 'firstBox' 값이 현재 상자로 업데이트되고 카운트가 1로 재설정된다.

마지막으로 전체 배열이 한 번에 종료될 수 있는 경우 현재 개수와 함께 'Math.max()' 함수를 사용하여 최대 개수가 반환시킨다.

수정한 코드는 이전 코드와 비교하여 큐 데이터 구조를 사용하지 않고 배열을 직접 탐색한다.

function paveBox(boxes) {
  let firstBox = boxes[0]; // 첫 번째 박스를 초기값으로 설정
  let count = 0; // 한 번에 나갈 수 있는 상자의 수
  let maxCount = 0; // 최대 한 번에 나갈 수 있는 상자의 수
  // 배열을 탐색하면서 한 번에 나갈 수 있는 상자의 수를 계산
  for(let i = 0; i < boxes.length; i++) {
    if(firstBox >= boxes[i]) { // 첫 번째 박스보다 작은 경우
      count++; // 한 번에 나갈 수 있는 상자의 수 증가
    } else { // 첫 번째 박스보다 큰 경우
      if(maxCount < count) { // 현재까지의 최대 상자 수와 비교
        maxCount = count; // 최대 상자 수 업데이트
      }
      firstBox = boxes[i]; // 첫 번째 박스 업데이트
      count = 1; // 카운트 재설정
    }
  }
  // 현재 카운트와 최대 카운트 중 큰 값을 반환
  return Math.max(count, maxCount);
}

레퍼런스 코드

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);
}