[Javascript] 프로그래머스 디스크 컨트롤러

 

문제

programmers.co.kr/learn/courses/30/lessons/42627#

코딩테스트 연습 - 디스크 컨트롤러

'하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.'라는 제한 사항이 이 문제를 푸는데 핵심이라고 생각한다.

• 요청 시점이 빠른 순서대로 작업을 정렬할 것
• 다른 작업을 처리하느라 이미 요청 시점을 지나버린 경우, 해당 작업은 waitQueue에 적재할 것
• waitQueue에 있는 작업들을 처리할 때 소요 시간이 작은 작업부터 처리할 것
• 디스크가 현재 일을 안 하고 있다면, waitQueue에 있는 작업을 처리할 것
• jobQueue에 작업이 남아있다면, waitQueue에 있는 작업을 한 번에 처리하지 말 것

 

마지막 조건은 이 문제를 풀면서 헤맸던 부분과 관련있기 때문에 일부러 추가했다. jobQueue에 작업이 남아있는데 waitQueue에 있는 작업을 한 번에 처리하려고 한다면 발생할 수 있는 문제는 무엇일까? 쉽게 얘기하면 waitQueue에 있는 작업들을 처리하느라 정작 jobQueue에서 당장 처리할 수 있는 작업을 처리하지 못하게 된다. 이 조건들을 생각하면서 작성한 코드는 아래와 같다.

 

풀이 과정

---

[ 221003 다시 풀어봄 ]

heap 카테고리에 있어 해당 알고리즘으로 풀려고 노력했으나 코드가 너무 길어져 포기.

코드가 살짝 더 짧아진 것 외에는 예전에 풀었던 방식과 크게 다른 점은 없다.

>> 현재와 요청시각이 가까운 작업 우선수행 & 현재가 요청시각 이후면 작업시간이 짧은것 우선수행 <<

function solution(jobs) {
    let answer = 0;
    let sorted = [...jobs.sort((a, b) => a[0] - b[0] || a[1] - b[1])];
    let now = 0, wait = [], work = null;
    
    while(true) {
        // 진행중인 작업 없을 때
        if (work === null) {
            // 대기작업 확인. 소요시간이 제일 작은 작업 수행.
            if (wait.length) {
                work = wait.shift();
            // 대기작업이 없다면 예정작업 확인.
            } else if (sorted.length) {
                work = sorted.shift();
            };
        };
        // 진행중인 작업 있을 때
        if (work !== null) {
            answer += work[0] > now ? work[1] : now - work[0] + work[1];
            now = work[0] > now ? work[0] + work[1] : now + work[1];
            work = null;
        };
        // 요청시간 지난 작업은 wait에 옮기기.
        while(sorted.length && sorted[0][0] < now) {
            wait.push(sorted.shift());
        }
        // wait에 있는 작업은 소요시간 기준 오름차순 정렬.
        wait.sort((a, b) => a[1] - b[1]);

        if (!sorted.length && !wait.length) break;
    };
    
    return Math.floor(answer/jobs.length);
}

---

function solution(jobs) {
    let answer = 0;
    let jobsCnt = jobs.length;
    // 요청시간이 빠른 순서대로 정렬하되 작업의 요청시간이 동일한 경우, 소요시간 기준 오름차순 정렬
    let jobQueue = jobs.sort((a, b) => {
        if (a[0] === b[0]) { return a[1] - b[1] };
        else { return a[0] - b[0] };
    });
    let curTime = jobQueue[0][0];
    let waitQueue = [];

    while (jobQueue.length > 0) {
        let job = jobQueue[0];
        // 현재시간이 작업의 요청시간을 지나버렸다면, waitQueue에 작업을 적재
        if (curTime > job[0]) {
            waitQueue.push(job);
            jobQueue.shift();
        // 현재시간이 작업의 요청시간을 지나지 않았다면,
        } else {
            // waitQueue에 작업이 있을 경우 작업 소요시간 기준 오름차순 정렬
            if (waitQueue.length > 0) {
                waitQueue.sort((a, b) => a[1] - b[1]);
                // waitQueue에 있는 작업 '1개'만 처리
                let waitJob = waitQueue.shift();
                curTime += waitJob[1];
                answer += curTime - waitJob[0];
            // waitQueue에 없으면 바로 작업 처리
            } else {
                curTime = job[0] + job[1];
                answer += job[1];
                jobQueue.shift();
            }
        }
        
        // jobQueue에 작업이 없고 waitQueue에 작업이 쌓여있다면 waitQueue에 있는 작업 모두 처리
        if (jobQueue.length === 0 && waitQueue.length > 0) {
            waitQueue.sort((a, b) => a[1] - b[1]);
            while (waitQueue.length > 0) {
                let waitJob = waitQueue.shift();
                curTime += waitJob[1];
                answer += curTime - waitJob[0];
            }
        }
    }
    
    return parseInt(answer / jobsCnt);
}

 

 

테스트케이스