이번 주에 배운 자료구조가 너무 어려워서 멘붕이었다.
예제의 레퍼런스 코드를 보며 Step by Step으로 따라가보자!
박스 포장 [Queue]
마트에서 장을 보고 박스를 포장하려고 합니다. 박스를 포장하는 데는 폭이 너무 좁습니다. 그렇기에 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다.
불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다.
뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 합니다. 앞사람이 포장을 끝내면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다.
만약, 앞사람의 박스는 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
풀이
function paveBox(boxes) {
// 예시처럼 boxes에 [5, 1, 4, 6]이 들어온다고 가정한다.
let answer = [];
// 정답이 될 answer를 먼저 선언
while(boxes.length > 0) {
// boxes의 길이가 0보다 크다면, 계속 반복한다.
let finishIndex = boxes.findIndex(fn => boxes[0] < fn);
// finishIndex = 박스 포장이 끝난 인덱스를 찾는 로직으로, boxes[0]보다 큰 인덱스의 수를 계속 찾아 재귀한다.
// [5, 1, 4, 6] 중 boxes[0]인 5보다 큰 인덱스 => 6 = boxes[3]
// finishIndex = 3
if(finishIndex === -1){
// 만약 찾지 못했다면 answer에 boxes 배열의 길이만큼 넣은 후, boxes 내부의 요소를 전부 삭제합니다.
// 이 상황에서는 else에서 짤리고 남은 boxes[0] = [6]이 이에 해당
answer.push(boxes.length); // answer.push(1) => answer = [3, 1]
boxes.splice(0, boxes.length); // boxes.splice(0,1) => boxes = [] =>
//이후 반복문 빠져나옴
} else {
// 만약 찾았다면, 한꺼번에 박스포장이 끝난 인원 수를 answer(결과 값)에 추가하고, 박스 포장이 끝난 인원 수 만큼 삭제해준다.
answer.push(finishIndex); // answer.push(3) -> answer = [3]
boxes.splice(0, finishIndex); // boxes.splice(0, 3) -> boxes = [6]
// 여기에서 잘리고 남은 boxes[0]의 [6]이 다시 while문으로 재순환
}
}
return Math.max(...answer);
// Array 형태인 answer를 Math.Max() 안에 Spread syntax 형태로 넣어 리턴
// answer = [3, 1]
// return 3
}