[Algorithm] Queue_박스 포장

유슬기·2023년 3월 14일

코드스테이츠

프론트엔드

목록 보기

59/64

문제

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

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

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

만약, 앞사람의 박스는 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

풀이

접근 방식

Queue 자료구조를 활용하여 선형 탐색을 진행한다.
Queue는 while문과 함께 활용되는 경우가 많다.

박스 포장대 대기열(boxes)는 모두가 동시에 이용할 수 있으나, 0번째 손님이 포장을 끝내고 나가야만 뒷 손님도 나갈 수 있다.
앞 손님이 포장을 마치고 퇴장할 때, 함께 퇴장하는 손님의 수를 기록 (변수 answer)
boxes이 모두 빌 때까지 0번째 손님보다 많은 박스를 포장하는 손님을 탐색
만약 0번째 손님보다 박스가 많은 손님이 없다면 모든 손님이 함께 나가므로, answer에 모든 손님의 인원수를 기록 + 박스 포장대의 모든 손님이 나감(boxes 비우기)
만약 0번째 손님보다 박스가 많은 손님이 있다면 answer에 해당 손님 앞까지 인원수를 기록 + 박스 포장대에서 해당 손님 앞까지 boxes 에서 제거
boxes이 빌 때 까지 위 작업을 반복

Code

function paveBox(boxes) {
	// 동시 퇴장 인원 수를 요소로 갖는 배열 answer 선언
	// boxes 전체를 순회하면서 퇴장이 이루어질 때 마다 동시 퇴장 인원수를 기록
    let answer = [];
    
    // 모든 인원이 포장을 마치고, 대기열이 빌 때까지 반복
    while (boxes.length > 0){
      	// boxes 배열의 첫 번째 요소부터 시작하여, 해당 요소보다 큰 값이 처음 나오는 인덱스를 찾기
        let finishIndex = boxes.findIndex(fn => boxes[0] < fn);
		// 만약 찾지 못했다면 answer에 boxes 배열의 길이를 넣은 후, boxes 내부의 요소를 전부 제거
        // boxes.length === 0이 되므로, while문 종료
        if(finishIndex === -1){
            answer.push(boxes.length);
            boxes.splice(0, boxes.length);
        // 만약 찾았다면, 해당 인덱스를 answer에 넣고, boxes에서 그 인덱스 앞까지 제외
        } else {
            answer.push(finishIndex);
            boxes.splice(0, finishIndex);
        }
    }

    // answer의 요소 중 가장 큰 값을 리턴
    // Math.max()메서드는 Number 타입의 인수를 받기 때문에 스프레드 연산자를 사용
    return Math.max(...answer);
}

정리

문제를 보고 첫 번째 boxes 요소보다 값이 큰 요소가 있으면 그 전 요소까지 함께 나가고, 함께 나가는 손님 수를 카운팅해서 가장 큰 카운팅 값을 리턴해야 하는 것 까지는 알겠는데... 딱 거기까지만 알겠더라...
페어분과 함께 1시간 넘게 고민하고 코드도 이리저리 바꿔가며 테스트를 돌려봤으나.. 진전이 없었다.

결국 레퍼런스를 보고 한 줄 한 줄 이해라도 하자! 며 레퍼런스 코드를 조심스레 열어보았다.
코드를 보고 입출력 예시를 그림으로 그려보면서 이해하니 조금이나마 머릿속에 개념이 잡히게 되었다.

다만, 아직도 이해가 되지 않는건 queue 자료구조는 데이터를 하나씩 넣고 뺄 수 있다고 했는데.. 위 코드에서 boxes를 큐라고 생각하고 구현했다고 이해했는데 그게 맞는지, 맞다면 splice로 손님(요소)들을 제외시킬 때 한 번에 여러 명(개)을 제외 시켜도 되는건지가 의문이다.

이 부분은 좀 더 찾아보고 확실해지면 첨언하겠다.