[자료구조] Queue_프린터

프린터의 인쇄 작업 목록의 크기와 최대 용량을 가정하고 각기 다른 용량의 문서를 차례대로 인쇄하여 모든 문서가 인쇄되는데 최소 몇 초가 걸리는지 테스트하는 문제이다. 자료구조의 queue를 학습할 때 대표적인 예시로 등장한다.

수도코드

first in first out 로직이므로 Queue 개념이 적용된 문제이다. 아래와 같이 그림을 그려가며 😂 수도코드를 작성해보았다.

풀이과정

이 문제의 포인트는...
아무 인쇄파일도 들어가지 않은 작업목록(queue)라는 배열에 일단 bufferSize만큼 0을 채워넣는 것이다!!!

이렇게 하고 1초가 흐를 때마다 queue.shift();를 해주면 이미 작업목록에 들어간 파일이 왼쪽으로 한 칸 움직일 것이다.

먼저 첫번째 작업파일을 빼와서 queue에 넣는 이 두 과정이 일어날 때 queue의 크기 & 시간이 지나는 것(1초씩)을 함께 변한다.

let currentDocu = documents.shift();
  queue.push(currentDocu); //일단 첫번째 document하나 넣고
  queue.shift(); //0 밀어내기
  let queueSum = currentDocu;
  count = 1 //요게 하나의 셋뚜

주석에 적어놓은 것처럼, 위 과정이 하나의 세트이다.

그런데, 이제 0번째 파일이 들어가고 난 다음 1번째 파일이 들어갈 때에는 조건에 따라서 두 케이스로 나뉘어진다.

• 작업용량이 널널할 때
• 작업용량이 꽉 차 있을 때

전자의 경우, 1번째 파일이 queue안에 들어갈 수 있고 이 때 0번째 파일처럼 일련의 과정이 진행된다.
후자의 경우, queue에 1번째 파일이 들어갈 수 없으므로 0을 채워넣어줌으로써 bufferSize를 유지시킨다.

여기서 또 중요한 것...!!!!

두 케이스로 갈라지기 전에 먼저 queue.shift();가 진행되어야지만!!!!!!!! 이 다음 작업파일이 들어갈 수 있을지 없을지 여부를 판단할 수 있다!!!!!

(맨 처음엔 shift 작업을 나중에 해줬더니 자꾸 결과값이 제대로 나오지 않았었다)

코드를 종합해보면...

function queuePrinter(bufferSize, capacities, documents) {
  // TODO: 여기에 코드를 작성합니다.
  // 인쇄작업목록에 들어가려고 대기중인 배열 = documents
  // 인쇄작업목록 = 숫자로 이루어진 배열, 길이가 bufferSize임, 배열요소의 모든 합이 capacities를 초과할 수 없음
  // 인쇄작업목록에서 배출되면 프린트
  // 초를 애초에 0을 초기값을 잡고 count를 하자~
  // 비어있는 칸에는 모두 0으로 세팅(dummy데이터를 넣는 것임)
  // 작업칸 이동은 어떻게 하지? 그냥 queue를 shift 해주면 됨


    let count = 0; 
  let queue = new Array(bufferSize).fill(0); //bufferSize 길이 만큼의 0으로 채워진 배열을 만든다(queue)

  let currentDocu = documents.shift(); //1. document에서 하나 뽑아와서
  queue.shift(); //2. 먼저 0 밀어내기
  queue.push(currentDocu); //3. 일단 첫번째 document하나 넣기
  let queueSum = currentDocu; //4. 
  count = 1 //5. 
  
  while(queueSum>0){
  
    currentDocu = documents.shift();
    queueSum = queueSum-queue.shift(); // queue에서 먼저 하나 제거해준 다음
    
    if(currentDocu + queueSum <= capacities){
      queue.push(currentDocu) //currentDocu를 넣는다
      queueSum = queueSum+currentDocu; //나가고 빠지는게 있으니까 queueSum 코딩식이 두번임!!!
      count++  
    } 
    
    else {
    queue.push(0)//capa를 초과하면 currentDocu 못 넣음. 따라서 0을 넣어주고
    //여기선 queueSum 변화 없음.
    documents.unshift(currentDocu)//다시 들오가!*****
    count++
    }
  
  }
  
  return count;
}