[Algorithm] Queue 알고리즘 문제, 박스 포장 Javascript

 

 

문제

 

박스를 포장하는 긴 줄이 있다고 가정한다. 박스를 포장하는 공간이 협소하기 때문에 들어온 순서대로 포장을 마치고 나가야 한다. 들어온 사람들은 모두 포장을 할 수 있지만, 가장 먼저 들어온 사람이 포장을 완료해야 이 후 포장을 마친 사람들도 나갈 수 있다.

 

뒷 사람이 포장을 완료하였어도, 첫 사람이 포장을 다 완료하지 못했다면 대기해야 하는 상황이다. 예를 들어 앞 사람이 포장해야 할 박스가 3개고 2번째 사람이 포장해야할 박스가 1개라면, 첫 사람이 3개의 박스 포장을 완료한 후 같이 나갈 수 있다.

 

전체 박스를 포장해야하는 사람들 중 한번에 몇명씩 나갈 수 있는지 최대값을 반환하라.

 

제약조건

1 <= 사람수 <= 10,000   |   1<= 박스 수 <= 10,000

 

소스 코드 구현

 

알고리즘 문제는 문제를 그대로 받아들이기 보다, 논리적인 흐름을 먼저 생각하는게 우선이다. 그리고 문제를 단순화 시켜야 한다.

문제에서 말하고 있는 자료구조는 Queue다. 새로운 사람은 뒤에서 추가되지만, 포장을 완료한 사람은 앞으로 나가게 된다.

사람들이 나갈 수 있는 조건을 생각해보면, 대기열 중에서 가장 큰 포장을 가진 사람 앞 대기열은 한번에 나갈 수 있다.

만약 첫번째 사람의 박스 수가 가장 많다면 대기열이 한번에 나갈 수 있다. 

만약 첫번째 사람의 박스 수가 두번째로 많다면 가장 많은 사람 앞까지 한번에 나갈 수 있다.

만약 첫번째 사람의 박스 수가 가장 적다면 자신(1명)만 나갈 수 있다.

 

① 소스코드 구현은 주어진 배열에서 첫번째 요소와 나머지 요소를 반복해서 비교한다.

② 만약 첫번째 요소가 가장 크다면 배열 전체의 길이를 result 배열에 담는다.

③ 만약 첫번째 요소외 큰 요소가 있다면, 그 앞까지의 갯수를 result 배열에 담고, 가장 큰 수의 index 까지 배열을 자른다.

④ 전체 배열이 0이 될 때 까지 반복한다.

 

function paveBox(boxes) {
    
    // 반환할 결과값
    let result = [];
    
    while(boxes.length > 0){

    	// 첫번째 값과 비교
        const idx = boxes.findIndex((item)=>item>boxes[0]);

		// 첫번째 값이 가장 큰 경우
        if(idx === -1){
            result.push(boxes.length);
            boxes.splice(0, boxes.length);
            
        // 첫번째 값보다 큰 경우가 있으면, 
        }else{
            result.push(idx);
            boxes.splice(0, idx);
        }
    }

	// 경우의 수 중 가장 큰 값을 반환한다.
    return Math.max(...result);
}

 

 

 

정리

 

처음 문제 접근 시 전체 배열을 1씩 증가시키는 로직을 짜고 있었다. 문제 단순화를 하지 못한 것이다. 현실 문제를 물어보는 알고리즘 문제에서는 현실 처럼 생각하기보다 추상화해서 생각하는 과정이 필요하다.

 

박스를 포장하기 위해 줄을 선 대기열을 Queue 자료구조라고 추상화 하고, 포장 후 나가는 인원의 수의 기본적인 원칙을 발견해서 코드로 구현하는 과정이 생각보다 시간이 많이 소요되었다.

 

 

 

 

[Algorithm] Data Structure and Algorithm Stack vs Queue