[Queue] 트럭문제, 프린터문제

프린터 (유사 문제 : 트럭 다리 지나기)

김코딩은 최근 인쇄할 일이 많이 생겨 창고에서 안 쓰던 프린터를 꺼냈습니다. 이 프린터의 성능을 테스트하여 새로운 프린터를 장만할지 결정하려고 합니다. 김코딩은 프린터의 인쇄 작업 목록의 크기와 최대 용량을 가정하고 각기 다른 용량의 문서를 차례대로 인쇄하여 모든 문서가 인쇄되는데 최소 몇 초가 걸리는지 테스트하기로 했습니다. 프린터 인쇄 작업 목록의 제한사항은 다음과 같습니다.

[제한사항]

인쇄 작업 목록은 칸으로 이루어져 있습니다.
각 칸에는 한 개의 문서만 위치할 수 있습니다.
문서는 1초에 한 칸만 이동할 수 있습니다.
인쇄 작업 목록의 크기는 bufferSize이고 최대 용량 capacities 만큼 문서를 담을 수 있습니다.
만약, 인쇄 작업 목록의 크기가 2이고 최대 용량이 10Kib라면 크기가 [7, 4, 5, 6] Kib인 문서들이 최단 시간 안에 순서대로 모두 인쇄되는 과정은 다음과 같습니다.

• 1초가 지나면 인쇄 작업 목록에는 7Kib 크기의 문서가 추가됩니다.
• 2초일 때 인쇄 작업 목록의 최대 용량이 10Kib이기 때문에 4Kib 문서는 작업 목록에 들어갈 수 없습니다. 동시에 7Kib 문서는 작업 목록에서 1칸 앞으로 이동합니다.
• 3초일 때 7Kib 문서는 인쇄 작업 목록에서 나와 프린터가 인쇄합니다. 동시에 4Kib 문서는 인쇄 작업 목록에 추가됩니다.
• 4초일 때 4Kib 문서는 인쇄 작업 목록에서 1칸 앞으로 이동합니다. 동시에 5Kib 문서는 인쇄 작업 목록에 추가됩니다.
• 5초일 때 4Kib 문서는 인쇄 작업 목록에서 나와 프린터가 인쇄합니다. 동시에 5Kib 문서는 인쇄 작업 목록에서 1칸 앞으로 이동합니다. 최대 용량 10Kib 제한으로 6Kib 문서는 인쇄 작업 목록으로 추가될 수 없습니다.
• 6초일 때 5Kib 문서는 인쇄 작업 목록에서 나와 프린터가 인쇄합니다. 동시에 6Kib 문서가 인쇄 작업 목록에 추가됩니다.
• 7초일 때 6Kib 문서는 인쇄 작업 목록에서 1칸 앞으로 이동합니다.
• 8초일 때 6Kib 문서가 마지막으로 인쇄됩니다.

위 예시에서와 같이 모든 문서가 출력되는데 걸리는 최소 시간은 8초가 걸립니다.

김코딩이 가지고 있는 프린터의 제한사항인 인쇄 작업 목록의 크기 bufferSize, 최대 용량 capacities가 주어집니다. 인쇄할 문서의 크기가 나열된 배열 documents가 모두 인쇄되는데 걸리는 최소 시간을 반환하는 솔루션을 만들어 주세요.

입력 값
인자1: bufferSize
Number 타입의 인쇄 작업 목록 크기
인자2: capacities
Number 타입의 인쇄 작업 목록에 추가될 수 있는 최대 용량
인자3: documents
Number 타입을 요소로 갖는 문서 크기가 나열된 배열
출력 값
Number 타입을 리턴해야 합니다.
주의사항
bufferSize는 1 이상 100 이하입니다.
capacities는 100Kib 이하입니다.
인쇄할 문서의 개수(배열의 길이) 1이상 100 이하입니다.
문서 하나의 크기는 capacities를 초과하지 않습니다.

입출력 예시

let bufferSize = 2;
let capacities = 10;
let documents = [7, 4, 5, 6];
let output = queuePrinter(bufferSize, capacities, documents);
console.log(output) // 8

답안코드

function queuePrinter(bufferSize, capacities, documents) {
  // TODO: 여기에 코드를 작성합니다.
  let timer = 0;   //걸린시간
  let print = [];  //프린터상태
  let printSum = 0;//현재 프린터 용량
  //프린트 크기만큼 0을 집어넣음
  for(let i = 0; i < bufferSize; i++){
    print.push(0);
  }
  //현재 걸려있는 문서
  let now_print = documents.shift();
  //
  //큐에 문서를 넣고 0을 하나 뺀다.
  print.unshift(now_print);
  print.pop();
  //
  //문서 용량 증가
  capacitiesSum += now_print;
  //시간 증가
  timer++;
  //더 이상 넣을 문서가 없을때까지 무한 루프
  while(capacitiesSum){
  //
    printSum -= queue.pop();      //문서프린트 완료
    now_print = documents.shift();//새 프린트 집어넣음
  //현재 집어넣은 프린터를 전체에 추가했을때 프린트 용량보다 작거나 같으면
    if(now_print+capacitiesSum <= capacities){
      queue.unshift(now_print);    //queue에서 빼고
      capacitiesSum+=now_print;    //프린트에 넣음
    }
    else{                          //프린트 용량을 넘어선다.
      print.unshift(0);            //0을 넣고
      documents.unshift(now_print);//새 프린트를 밀어넣는다.
    }
    timer++;                       //시간이 지난다.
  }
  return timer;                    //모든 프린트가 끝나면 시간리턴
}

인쇄 작업 목록의 크기가 2이고 최대 용량이 10Kib라면 크기가 [7, 4, 5, 6] Kib인 문서들이 최단 시간 안에 순서대로 모두 인쇄되는 과정

위의 출력예제를 코드로 나타내면, queuePrinter(2,10,[7,4,5,6])이고, 그림으로 나타내보면 다음과 같다.

documents에서 하나를 뽑아서, now_print에 넣어주고 print안의 총합과 더해서 capacities보다 작거나 같으면 밀어넣고 0을 빼준다. 만약에 크면 0을 빼주고 print안에서 한칸씩 옮긴다. 그리고 1초를 증가시킨다. 넣을때랑 빠질때는 시간을 재지 않고, 한칸 이동할 때마다 1초씩 세준다. 결과적으로 print안의 합이 완전히 0이 될때까지 무한루프를 돌리는 과정이다. JavaScript라는 언어는 동적으로 배열을 할당하기때문에, 크기를 미리잡아두는 것이 어려운 모양이다. 원래 C나 C++이었다면, null값을 삽입하고 공백배열 bufferSize 갯수 크기로 메모리를 잡았을텐데, 0으로 채워넣어서 해결하는 것이 신기했다.

느낀점

초기에는 queue를 어떤식으로 사용해야할지 잘 몰랐으나, 데이터 처리가 완료된 뒤에 빼는 식으로 생각하면 괜찮을 것 같다. 이건 프린터기의 구동방식처럼 구현했을 뿐이고, node search를 할때에는 search하지 않은 걸 큐에 넣고 search하면 빼고, 안한걸 다시집어넣고. search를 위한 buffer 공간으로 사용될 수 있을 것 같다.