자료구조 04

어려운 자료구조 문제를 정리.

04_[Queue] 동화책 출간

문제


동화책 전문 회사 동화스테이츠의 출간팀은 동화책 출간 작업을 하고 있습니다. 각 동화책 출간 진도가 100%일 때 출간할 수 있습니다.
각 동화책 출간 담당자는 다르며, 담당자의 업무 속도도 다르기 때문에 커리큘럼 순서 상 뒤에 있는 책이 앞에 있는 책보다 먼저 출간이 완료될 수 있습니다.
이때, 뒤에 있는 책은 앞에 있는 책이 출간될 때 함께 출간됩니다.

[예시]

개선 작업이 30% 진행된 책을 하루에 20% 작업할 수 있는 담당자가 맡을 경우 3일간 작업 후 4일째 출간할 수 있고 50% 작업할 수 있는 다른 담당자가 맡을 경우에는 2일째 출간할 수 있습니다.
개선 작업이 95% 진행된 책을 하루에 1% 작업할 수 있는 담당자가 맡고 30% 진행된 다음 책을 하루에 30% 작업할 수 있는 다른 담당자가 맡는다면 5일째에 두 개 책이 출간됩니다.
며칠 째에 출간하는 건 아무런 상관이 없습니다. 다만, 그날에 몇 개가 출간되는지는 아주 중요합니다.
4일째에 출간할 수 있는 책이 0 번째에 있고, 2일째에 출간할 수 있는 책이 1 번째에 있다면 4일 하루동안 출간할 수 있는 책은 2권입니다.
커리큘럼 상 먼저 배포되어야 하는 순서대로 동화책 출간 진도가 나열된 배열 books와 각 동화책 출간 담당자의 업무 속도가 나열된 배열 speeds가 주어질 때 한 번에 몇 개의 책이 배포될 수 있는지를 반환하는 improveBook 함수를 완성해 주세요.

주의사항


동화책 출간 진도는 100 미만의 자연수입니다.
담당자 업무 속도는 100 이하의 자연수 입니다.
개선해야 하는 동화책 출간의 개수는 100개 이하입니다. (books, speeds 배열의 길이)
각 동화책 출간는 커리큘럼 상의 먼저 배포되어야 하는 순서대로 나열됩니다.
업무 속도는 해당 동화책 출간 담당자가 하루 동안 작업할 수 있는 작업량의 비율입니다.
배포는 배포될 수 있는 개선 완료된 책을 모아 하루에 한 번만 할 수 있습니다.
speeds와 books 배열의 인덱스를 기준으로 동화책과 담당자가 정해집니다.
books[0]번째 동화책 출간을 speeds[0]번째 담당자가 맡습니다. 만약, books[0]이 97이고 speeds[0]이 1이라면, 해당 책은 4일 뒤에 한꺼번에 출간됩니다.

입출력 예시


let books = [93, 30, 55];
let speeds = [1, 30, 5];
// 각각 7일, 3일, 9일 뒤에 출간할 수 있습니다.
// 7일째에 출간할 수 있는 책은 2권이고, 9일째에 츨간할 수 있는 책은 1권입니다.
let output = improveBook(books, speeds);
console.log(output); // [2, 1]

books = [95, 90, 99, 99, 80, 99];
speeds = [1, 1, 1, 1, 1, 1];

output = improveBook(books, speeds);
console.log(output); // [1, 3, 2]

Referencecode


function improveBook(books, speeds) {
    let answer = []; 
    let workDay = [];
    let quotient = 0;
    let remainder = 0;
    
    // books 배열을 순회합니다.
    for(let i = 0; i < books.length; i++) {
        // 각 담당자마다 책이 발행되는 시간을 계산합니다.
        quotient = Math.floor((100 - books[i]) / speeds[i]);
        remainder = (100 - books[i]) % speeds[i];
        
        // 만약 나머지(remainder)가 0보다 크면 몫(quotient)에 1을 더합니다.
        if(remainder > 0){
            quotient = quotient + 1;
        }
        
        // workDay 배열에 차례대로 담습니다.
        // workDay 배열은 books배열에서 책이 발행되는 시간만을 추출해 넣은 배열입니다.
        workDay.push(quotient);
    }
    
    // workDay 배열이 0보다 클 때까지 반복합니다.
    while(workDay.length > 0){

        // workDay에서 0번째 인덱스보다 큰 크기의 인덱스를 찾아 deployIndex에 할당합니다.
####         let deployIndex = workDay.findIndex(fn => workDay[0] < fn);
        
        if(deployIndex === -1){
            // 만약 찾지 못했다면 answer에 workDay 배열의 길이를 넣은 후, workDay 내부의 요소를 전부 삭제합니다.
            answer.push(workDay.length);
            workDay.splice(0, workDay.length);

        } else {
            // 만약 찾았다면, 해당 인덱스를 answer에 넣고, workDay에서 그만큼 제외합니다.
            answer.push(deployIndex);
            workDay.splice(0, deployIndex);
        }
    }

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

좋은 웹페이지 즐겨찾기