Queue 알고리즘 프린터 문제

 

문제

 

 

 

풀이

 

① 그림 그려보기

 

② Code

function queuePrinter(bufferSize, capacities, documents){
    // 변수 선언
    let count = 0;
    let queue = Array(bufferSize).fill(0);
    let totalBufferVolume = 0;
    const calculateToalSize = (array) => array.reduce((acc, cur)=>{return acc+cur},0)

    // 최초 1번만 실행됨
    let currentDocument = documents.shift();

    queue.unshift(currentDocument);
    queue.pop();

    totalBufferVolume = calculateToalSize(queue);

    count++;

    // 2번째 부터 totalBufferVolume이 0이 될 때까지 반복
    while(totalBufferVolume){

        // 전체 용량에서 빠져나간 문서 용량 제거
        totalBufferVolume = totalBufferVolume - queue.pop();
        
        // 현재 문서 설정
        currentDocument = documents.shift();
        
        // 전체 사이즈+추가된 문서 용량이 capacities 보다 작아야 함
        if(totalBufferVolume + currentDocument <= capacities){
            // 1) queue에 문서 추가
            queue.unshift(currentDocument);
            // 2) 전체 용량에 문서 용량 추가            
            totalBufferVolume += currentDocument;
        }else{
            // 다시 documents에 현재 문서 추가(Roll Back 처럼)
            documents.unshift(currentDocument);
            // queue에도 다시 0을 추가함(Roll Back 개념)
            queue.unshift(0);
        }
        // 1초가 지났다
        count++;
    }


    return count;
}

• buffersize 길이를 가진 Queue 배열 생성
• calcualteTotalSize()는 배열의 문서 사이즈 총합을 반환함
• 최초 1회는 while 문 밖에서 로직 구성
  • 최근 문서를 Queue에 추가해줌.
  • Queue에서 문서 하나를 제거함
  • 전체 용량 계산 후 1초 증가
• 2회째 부터는 while문을 돌면서 전체 용량이 0이 될 때 까지(출력이 완료될 때 까지) 반복함
  • 만약 새로 추가된 문서가 용량 제한에 걸리면 배열 구성을 다시 해줌
    • documents에 원래 문서를 다시 가져다 놓음
    • queue에도 0을 다시 추가함
• 마지막으로 count를 증가시키면서 시간 증가를 구현하고 반환함

 

🚀️ 도움이 되셨다면 구독과 좋아요 부탁드립니다 👍️