[자료구조] Queue_도서 출간

어떠한 배열 두 개(books, speeds)가 있다.

• 인자 1:books
  Number 타입을 요소로 갖는 '퍼센트' 단위의 동화책 출간의 현재 진도가 나열된 배열
• 인자 2: speeds
  Number 타입을 요소로 갖는 '퍼센트' 단위의 동화책 출간 담당자의 '하루'에 작업할 수 있는 업무 속도가 나열된 배열

커리큘럼 순서 상 뒤에 있는 책이 앞에 있는 책보다 먼저 출간이 완료될 수 있다
이 때, 뒤에 있는 책은 앞에 있는 책이 출간될 때 함께 출간된다.

함수의 전달인자로 들어가고 이 함수는 모든 스프린트가 배포되는 날까지, 배포가 가능한 날에 배포될 수 있는 스프린트 수를 나열한 배열이 출력값이다.

수도코드

//예시를 들어보자면
//books = [95, 90, 99, 99, 80, 99];
//speeds = [1, 1, 1, 1, 1, 1];
//queue = [5, 10, 1, 1, 20, 1] --> [10, 1, 1, 20, 1]--> [20, 1]-->[] 
//결론: 매 step 당 shift되는 개수가 출력인데, step의 기준은.. 
//최대값보다 큰 게 나타날때까지!
//쌓아놨다가 한꺼번에 shift되는 개념은? step 마다 shift되는 개수로 접근하지 말고 index로 접근하자

풀이과정

일단 빈 배열 queue를 선언해주고 각 books&speed 배열 요소를 훑으면서 책이 출간되기까지 걸리는 기간을 구해 queue에다가 요소로 추가해주었다.

const queue = [];

  //1. queue는 걸리는 기간임. 배열만들어주기
  for(let i=0; i<books.length; i++){
    queue.push(Math.ceil((100-books[i])/speeds[i])) //소수점일 때 올림
  }

새로운 빈 배열 result를 또 선언해주고, 책이 출간될 때의 개수를 push해주기로 했다. 이 때 queue에서는 그 만큼 요소들이 제거 된다.
계속해서 삭제되어져 빈배열이 될 때까지 아래 내용을 반복한다.

• queue에서 일단 0번째 인덱스값보다 큰 첫 번째 요소의 인덱스를 구한다 --> maxValue라고 선언하고 바로 그 값 할당

• maxValue를 찾으면?

  • result에다가 그 인덱스를 push
  • queue 배열에서 0부터 해당 maxValue인덱스만큼 제거

• maxValue를 못 찾으면?

  • result에다가 남은 queue의 길이만큼 push
  • queue 배열에서 0부터 queue 길이만큼 제거

 let maxValue = queue.findIndex(fn => queue[0] < fn);
        
    if(maxValue === -1){

      result.push(queue.length);
      queue.splice(0, queue.length) //잘라내버림

    } else {
      result.push(maxValue);
      queue.splice(0, maxValue) 
    }

코드를 종합해보면

function improveBook(books, speeds) {
  // TODO: 여기에 코드를 작성합니다.

  //books = [95, 90, 99, 99, 80, 99];
  //speeds = [1, 1, 1, 1, 1, 1];
  //queue = [5, 10, 1, 1, 20, 1] --> [10, 1, 1, 20, 1]--> [20, 1] 결론: 매 step 당 shift되는 개수가 출력인데, step의 기준은.. 

  const queue = [];

  //1. queue는 걸리는 시간임. 배열만들어주기
  for(let i=0; i<books.length; i++){
    queue.push(Math.ceil((100-books[i])/speeds[i])) //소수점일 때 올림
  }

  //2. queue를 순회하면서 maxValue와 비교하기
let result = [];
 while(queue.length > 0){

        let maxValue = queue.findIndex(fn => queue[0] < fn);
        
        if(maxValue === -1){
            result.push(queue.length);
            queue.splice(0, queue.length) //잘라내버림

        } else {
            result.push(maxValue);
            queue.splice(0, maxValue) 
        }
    }

    // 결과물을 반환합니다.
    return result;
}

이해가 안 가는 부분...
queue.splice(0, maxValue) 대신에
queue = queue.slice(maxValue, queue.length)를 하면 왜 에러가 나는건지 알아봐야겠다

직관적으로 풀기

사실 이 문제는 레퍼런스 코드를 먼저 보고 이해한 다음 나만의 방식으로 다시 풀어본 문제였다.

indes값으로 접근하는 것은 처음에 쉽게 떠올릴 수 있는 방법은 아니기 때문에 count하는 방식으로 아래와 같이 접근해보았다.

function improveBook(books, speeds) {
  
  const queue = [];

  //1. queue는 걸리는 시간임. 배열만들어주기
  for(let i=0; i<books.length; i++){
    queue.push(Math.ceil((100-books[i])/speeds[i])) //소수점일 때 올림
  }

  let result = [];  
  let maxValue = queue.shift();
  let count = 1; 

    while(queue.length>0){
      let checkValue = queue.shift(); //일단 빼고나서 maxValue와 비교
      
      if(maxValue < checkValue){
        maxValue = checkValue;
        result.push(count) //이전count 값은 result로 밀고
        count = 1;      // 새롭게 1할당. checkValue가 queue에서 빠진 상태니까 count 초기값이 1임.  
      }

      else{ 
        count++ 
      }
  }
  result.push(count) //count가 추가되지 못하고 while문이 종료됨. 따라서 최종 count 값을 push
  return result;
}