디스크 컨트롤러 - 왜 그렇게 풀리는가? 개념 알아보기 [프로그래머스]

 

문제를 풀고 나서 인터넷에 풀이들을 찾아 봤습니다.

'이 방식을 쓰면 된다'는 풀이들은 많았으나, 왜 그렇게 풀면 풀리는지에 대해 이유를 설명한 글을 찾아보기가 어려워서 이렇게 글을 포스팅하게 되었습니다.

 

본문에는 풀이법과 정답 코드가 포함되어 있으니, 열람을 원치 않는 분들께서는 주의하여 주시기 바랍니다.

 

문제 보러 가기 >

 

 

 

개념 풀이

문제의 조건에 따르면, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법을 찾아야 합니다.

 

한 번에 한 작업씩만 들어온다면 우선 순위가 필요 없겠지만,

현재 작업을 진행하는 도중에 여러 작업 요청이 있을 수 있습니다.

따라서 우선 순위에 따라 처리해야 하는데요.

 

우선 순위를 처리하는 정답부터 말씀드리자면, 현재 작업이 진행되는 동안 요청된 작업들 중에 가장 소요시간이 짧은 작업을 선택해야 합니다.

 

왜 그럴까요?

 

아래 표와 같은 작업 목록이 있다고 가정하겠습니다.

요청 시점	소요시간
0	10
7	1
9	2

처음 요청된 작업은 10ms에 끝납니다.

첫 작업이 진행되는 동안에 새로 요청된 작업이 두 개 있습니다.

7ms에 요청된 소요시간 1ms짜리 작업과

9ms에 요청된 소요시간 2ms짜리 작업입니다.

 

문제 조건을 다시 생각해 보면,

작업의 요청부터 종료까지 걸린 시간(이하 '실행시간'이라고 하겠습니다)의 평균을 가장 적게 만들어야 합니다.

평균을 낮추려면 총합을 낮춰야겠죠. (평균 = 총합 / 작업 수)

따라서 합을 낮추는 방법을 찾아보겠습니다.

 

하드디스크가 처리중인 작업이 없을 경우에는 먼저 요청된 작업이 시작되므로, 처음 실행되는 작업은 [0, 10] 입니다.

작업이 끝나는 10 시점에 [7, 1]짜리 작업을 먼저 시작하면, 해당 작업의 실행시간은 4입니다. (요청시점 7 ~ 종료시점 11)

반면 [9, 2]짜리 작업을 먼저 시작하면, 해당 작업의 실행시간은 3으로 더 짧습니다. (요청시점 9 ~ 종료시점 12)

 

얼핏 생각해서는, 실행시간이 짧은 [9, 2] 작업을 먼저 선택하는 방식이 유리할 거란 생각이 들 수도 있습니다.

하지만 소요시간이 짧은 [7, 1] 작업을 선택해야 유리합니다.

왜냐하면 작업의 소요시간이 남은 작업들의 실행시간에 더해지는 꼴이 되기 때문입니다.

 

예시로 살펴보겠습니다.

 

[7, 1] 작업을 먼저 시작할 경우 다음 작업의 시작 시간은 10에서 소요시간 1이 더해진 11이 됩니다.

[9, 2] 작업은 11에 시작되어 13에 끝납니다. 실행시간은 3에서 4로 1 증가합니다. (요청 9 ~  종료 12 였는데 요청 9 ~ 종료 13이 됨)

 

[9, 2] 작업을 먼저 시작할 경우 다음 작업의 시작 시간은 10에서 소요시간 2가 더해진 12가 됩니다.

따라서 [7, 1] 작업은 12에 시작되어 13에 끝납니다. 실행시간은 4에서 6으로 2 증가합니다. (요청 7 ~ 종료 11 이었는데 요청 7 ~ 종료 13이 됨)

 

어떤 작업을 먼저 시작하든 간에, 종료되는 시점은 13ms로 같습니다. 하지만 중요한 것은 전체 작업의 종료시간이 아니라, 각 작업의 실행시간의 평균입니다.

[0, 10] -> [7, 1] -> [9, 2] 순으로 작업할 경우, 실행시간의 합은 10 + 4 + 4 = 18이 됩니다.

반면 [0, 10] -> [9, 2] -> [7, 1] 순으로 작업하면 실행시간의 합은 10 + 3 + 6 = 19가 됩니다.

따라서 현재 작업이 끝나는 시점에서 실행시간이 짧은 것이 아닌, 소요시간이 짧은 것을 선택하는 것이 실행시간의 평균을 가장 적게 만드는 방법임을 알 수 있습니다.

 

 

 

개념을 코드로 옮기기 (JavaScript)

현재 작업이 실행되는 동안 새로 들어온 작업 요청들 중에 소요시간이 가장 짧은 것이 먼저 올라오도록 하기 위해서, 최소 힙 자료구조를 사용하여 풀어 보겠습니다.

 

JS에는 힙 자료구조가 제공되지 않으므로, 클래스로 구현해서 풀어 보았습니다.

class Heap {
    constructor() {
        this.arr = [null];
    }
    push(req, dur) {
        const a = this.arr;
        a.push({
            req: req,
            dur: dur,
        });
        let i = a.length - 1;
        let pi = Math.floor(i/2);
        while (pi > 0 && a[i].dur < a[pi].dur) {
            const tmp = {...a[pi]};
            a[pi] = {...a[i]};
            a[i] = tmp;
            i = pi;
            pi = Math.floor(i/2);
        }
    }
    pop() {
        const a = this.arr;
        if (a.length <= 1) {
            return null;
        }
        const ret = {...a[1]};
        a[1] = {...a[a.length-1]};
        a.splice(-1);
        let pi = 1;
        let li = pi*2;
        let ri = pi*2+1;
        while (li < a.length) {
            let i = li;
            if (ri < a.length && a[li].dur > a[ri].dur) {
                i = ri;
            }
            if (a[i].dur < a[pi].dur) {
                const tmp = {...a[i]};
                a[i] = {...a[pi]};
                a[pi] = tmp;
                pi = i;
                li = i*2;
                ri = i*2+1;
            } else break;
        }
        return ret;
    }
    look() {
        return this.arr.length < 2 ? null : this.arr[1];
    }
}

 

어디서든 사용 가능한 일반적인(General) 힙은 아니고, 이 문제에 맞게 변형한 힙이지만 기본 원리는 똑같습니다.

 

일차원 배열을 완전 이진 트리처럼 활용한 구현입니다.

부모 노드와 자식 노드를 찾아갈 때의 편의성을 위해서, 배열의 인덱스 0은 null로 비워 두었습니다. 이렇게 하면 왼쪽 자식 노드의 인덱스는 부모 노드의 인덱스 * 2, 오른쪽 자식 노드의 인덱스는 부모 노드의 인덱스 * 2 + 1이 됩니다.

 

저는 힙에 단순히 소요시간만 저장하는 것이 아니라, 요청시점도 저장하고 싶었기 때문에 객체를 저장할 수 있도록 구현했습니다. JS에서 객체의 복사본을 만드는 것은 리소스를 많이 소모하는 일이죠... 이 문제에 한해서는 이런 구현 방식도 나쁘지 않다고 생각했습니다. 시간과 공간을 조금 더 소모하는 대신, 개발자가 사용하기 편한 코드를 짰습니다.

 

Heap.push(req, dur)를 통해 힙에 자료를 밀어넣을 수 있습니다. 가장 작은 값을 빼내는 건 Heap.pop()을 이용하면 됩니다.

 

Heap.look() 메서드는 해당 힙의 맨 처음을 확인할 수 있는 메서드입니다. 현재 힙에서 가장 작은 값을 반환하고, 힙에서 pop 하지 않습니다. 힙이 비어 있으면 null을 반환합니다.

 

위의 클래스를 이용한 문제 풀이 코드는 다음과 같습니다.

function solution(jobs) {
    jobs.sort((a, b) => a[0] - b[0]);
    const heap = new Heap();
    let currentEndTime = jobs[0][0];
    let sumOfElapsedTime = 0;
    let jobIndex = 0;
    while (true) {
        while (jobIndex < jobs.length && jobs[jobIndex][0] <= currentEndTime) {
            const job = {
                req: jobs[jobIndex][0],
                dur: jobs[jobIndex][1],
            };
            heap.push(job.req, job.dur);
            jobIndex++;
        }
        if (heap.look()) {
            const popped = heap.pop();
            const job = {
                req: popped.req,
                dur: popped.dur,
            };
            sumOfElapsedTime += currentEndTime - job.req + job.dur;
            currentEndTime += job.dur;
        } else if (jobIndex < jobs.length) {
            currentEndTime = jobs[jobIndex][0] + jobs[jobIndex][1];
            sumOfElapsedTime += jobs[jobIndex][1];
            jobIndex++;
        } else break;
    }
    return Math.floor(sumOfElapsedTime / jobs.length);
}

 

작업 하나를 잡고, 그동안 요청되는 작업들을 힙에 밀어 넣습니다.

그리고 현재 작업이 끝나면 다음에 실행될 작업을 힙에서 꺼냅니다.

그리고 요청 시점에서 종료 시점까지의 실행시간을 sumOfElapsedTime에 누적합니다.

힙이 비어 있다면, 요청시간이 가장 빠른 작업을 꺼내서 잡아 주면 됩니다. (문제에 '하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다' 라는 조건이 있습니다)

 

 

 

질문이나 피드백은 언제든 환영합니다!