[Algorithm] Queue 알고리즘 Printer Spooler 구현하기

 

 

문제

 

Queue 자료구조의 대표적인 활용 사례는 프린터 스풀러다. 출력할 문서들은 Printer Buffer에 차례대로 저장되고, 먼저 저장된 문서부터 출력이 시작된다.

입력으로는 bufferSize, capacities, 문서로 구성된 배열인 documents 3가지가 주어진다. 인쇄할 문서의 크기가 나열된 배열 documents가 모두 인쇄되는데 걸리는 최소 시간을 반환하라.

 

제한사항

• 인쇄 작업 목록은 칸으로 이루어져 있음
• 각 칸에는 한개의 문서만 위치가능
• 문서는 1초에 한 칸씩만 움직일 수 있음
• 인쇄 작업 목록의 크기는 bufferSize고 최대 용량 capacities 만큼 문서를 담을 수 있음
• 1<= bufferSize <= 100
• capacities <= 100KiB
• 문서 하나의 크기는 capacities를 초과하지 않음

 

소스 코드 구현

 

첫번째 소스코드다.2022.05.23 - [Algorithm] - [Algorithm] Queue 알고리즘 문제, 박스 포장 Javascript

모든 경우의 수를 while 문안에서 구현한 소스 코드다.

① 버퍼 사이즈 만큼의 배열을 만들고 null로 초기화 한다.

② 버퍼 내 문서가 존재하는 경우 한칸씩 이동한다.

③ 버퍼 내 문서 크기의 총합에 새로운 문서의 크기를 더한 값이 capacities보다 작은 경우와 queue에 문서를 추가할 자리가 있는 경우 Documents에서 새로운 문서를 Queue에 추가한다.

④ documents의 길이가 0 이하 && Queue에 문서가 없는 경우 반복문을 중단하고 count를 출력한다.

 

function queuePrinter(bufferSize, capacities, documents) {
    
   // Queue상의 문서 크기의 합이 capacitiy보다 큰지 확인
   let queue = new Array(bufferSize).fill(null);
   let count = 0;

   // 상태값이 변하는 경우 : documents / queue
   
   // 현재 Queue가 다 찼는지 확인

   // 한칸 앞으로 이동
   // documents가 다 찼거나 queue 내에 문서가 없으면 종료

   while(documents.length > 0 || queue.filter((item)=>item!==null).length > 0 ){
       count++;
  
  		// Debugging
       console.log(`
            queue : ${queue}
            documents : ${documents}
            count : ${count}
           `)

        // Spool 내 새로운 문서가 존재하면
        if(queue.filter((item)=>item!==null).length > 0){
            // Queue의 순서 이동 + 첫번째 요소 제거(출력)
            queue.shift();
            queue.push(null);
        }

        let bufferSum = queue.reduce((acc, cur)=>{ return acc+cur}, 0);
        // Queue에 새로운 요소 삽입
        if(bufferSum + documents[0] < capacities){
            // Queue의 빈 자리가 존재하면
            if(queue.filter((item)=>item===null).length > 0){
                // 뒷 빈자리에 새로운 요소를 추가한다.
                let newDocument = documents.shift();
                queue[queue.length-1]=newDocument;
            }
        }
   }

   return count;

}

 

 

두번째 소스코드다.

레퍼런스를 참고해서 첫번째 케이스는 while 문 밖에서 처리 후 2번째 이상 프로세스 부터는 while 문 내부에서 작동한다. 

 

① bufferSize를 가지는 Queue를 생성한다. / bufferTotal은 0으로 초기화 한다. / currentDocument는 documents의 첫번재 요소를 가져온다.

② 첫번째 케이스는 while 문 밖에서 처리한다. currentDocument를 queue에 삽입하고, 맨 앞 요소를 제거한다. queue에 삽입된 currentDocument를 합쳐 bufferTotal를 구한다. 카운터를 1 올린다.

③ while문은 bufferTotal이 0이 될 때 까지 반복한다.

④ queue의 앞 요소를 출력해서 bufferTotal에서 제외해주고, currentDocument는 documents의 첫 요소를 가져온다.

⑤ bufferTotal과 currentDocument를 합친 수가 capacities보다 작은 경우 Queue에 새로운 문서를 push하고 bufferTotal에도 추가해준다.

⑥ 만약 반대의 경우에는 documents에 다시 새로운 문서를 추가해주고 queue에는 0을 push 해준다. (한칸 앞으로 밀리는 상황)

⑦ bufferTotal이 0이 되면 count를 출력한다.

function queuePrinter(bufferSize, capacities, documents) {
    
    let queue = new Array(bufferSize).fill(0);
    let count = 0;
    let bufferTotal = 0;

    let currentDocument = documents.shift();


    queue.push(currentDocument);
    queue.shift();

    bufferTotal += currentDocument;

    count++;

    while(bufferTotal > 0){
        bufferTotal -= queue.shift();
        currentDocument = documents.shift();
        

        if(bufferTotal + currentDocument <= capacities){
            queue.push(currentDocument);
            bufferTotal += currentDocument;
        }else{
            documents.unshift(currentDocument);
            queue.push(0);
        }
        count++;
    }
    return count;

}

 

 

정리

 

알고리즘 문제를 잘 푸는 왕도는 없다. 다만 여러가지 문제를 접해보고 고민해보고, 시도를 하다보면 익숙해지는 것 뿐이다. 알고리즘 문제를 풀 때 효과적인 방법은 있다. 바로 프로세스를 줄글로 나열해보는 것이다. 머리속으로 추상적인 프로세스를 그리다보면 예외 처리를 놓치게 되는 경우가 많다.

아주 간단한 입력을 테스트 케이스로 프로세스가 어떻게 흘러가는지 글로 작성해본 후 프로세스를 소스코드로 변환해주면 된다. 즉, 수도코드(Pseudo Code)를 먼저 작성하고, 그 다음 컴퓨터가 이해할 수 있는 코드로 변환해가는 과정이 알고리즘 문제를 빠르게 풀 수 있는 방법이다.

 

 

 

 

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