[알고리즘] Queue로 포장을 마치고 나가는 인원 수 구하기

문제 설명

조건

- 사람들이 박스 포장을 하기 위해 한 줄로 서 있음

- 짐이 많은 사람은 포장하는 박수의 개수가 많아 포장 시간이 길어짐

- 장소가 협소하여 먼저 온 사람이 박스 포장을 마치고 나가야지 뒷 사람도 나갈 수 있음

- 뒷사람이 포장을 모두 끝내도 앞 사람이 끝내지 못하면 나갈 수 없음 

전달인자

- boxes : 앞 사람부터 차례로 포장해야 하는 박스 수가 담긴 배열

출력 값

- Number 타입을 리턴해야 하며 통틀어 최대 몇 명이 한꺼번에 나가는지 출력하기

 

코드 작성 포인트

방법1

- 전달인자 boxes가 queue가 되므로 따로 queue를 받을 변수를 선언할 필요는 없음

- queue에서 마지막으로 비워진 값을 담기 위한 last 변수 선언

- queue에서 곧 비워질 값을 받기 위한 변수 head 선언 (선택사항)

- 결과 값을 받을 count와 그것을 담기 위한 배열 result 선언

 

방법2

- 결과 값을 담기 위한 배열 result 선언

- findIndex 메소드를 이용 : queue에서 비워져야 할 엘리먼트 그룹의 바로 뒤에 있는 Index값 찾기

- 그 인덱스 값을 result 배열에 push로 삽입하여, queue에서 비워야 할 엘리먼트의 수를 바로 넣어주기

- splice 메소드를 통해 queue의 엘리먼트를 비우기 (splice는 mutable)

 

코드 작성하기

방법 1

function paveBox(boxes) {
  
  let head = ''    // queue의 0번 인덱스 값
  let last = ''    // queue에서 가장 최근에 나간 값
  let count = 0    // 한 번에 나가는 사람의 수
  let result = []  // 한 번에 나가는 사람의 수를 요소로 담을 배열
  
  while (boxes.length>0) {  // 전달인자 boxes가 queue에 해당됨
    
    // 한 번에 몇 명이 나갈 수 있는지 카운트 시작
    if (count===0) {        
    last = boxes.shift()
    head = boxes[0]
    count++
    } 
    
    // last보다 queue의 0번째 엘리먼트 값이 작으면 queue를 비우며 계속 카운팅
    else if (last>=head) {  
    boxes.shift()
    head = boxes[0]
    count++
      
      // queue의 길이가 0이 되면 while문이 종료되므로, count값을 보존하기 위해 push 해주기 
      if (boxes.length===0) { 
        result.push(count);
        break;
      }
    } 
    
    // last보다 queue의 0번째 엘리먼트 값이 크면 count를 초기화하고 다시 세기
    else {                    
      result.push(count);
      count = 0;
    }
    
  }
  return Math.max(...result);   // spread 문법으로 엘리먼트의 최대값 구하기
}

 

방법2

function paveBox(boxes) {
    let result = [];
    
    // queue인 boxes 배열이 0보다 클 때까지 반복
    while(boxes.length > 0){
        
        // findIndex 메소드를 사용해서 queue의 첫번째 요소보다 큰 엘리먼트의 인덱스 찾기
        let finishIndex = boxes.findIndex(fn => boxes[0] < fn);
        
        // 인덱스를 찾지 못했다면 queue가 한 번에 나가야 하므로 result에 boxes 배열의 길이 push
        // while 반복문이 종료되도록 boxes의 엘리먼트를 모두 비우기
        if(finishIndex === -1){
            result.push(boxes.length);
            boxes.splice(0, boxes.length); 

        } else {
            // 인덱스를 찾았다면 그것을 result에 넣고, boxes에서는 그 인덱스의 앞까지 비워주기
            result.push(finishIndex);
            boxes.splice(0, finishIndex);
        }
    }

    return Math.max(...result);   // spread 문법으로 엘리먼트의 최대값 구하기
}