Programmers_42627 디스크 컨트롤러

// 최소 힙 구현 
class MinHeap {
    constructor() {
        this.heap = [];
    }

    size() {
        return this.heap.length;
    }

    swap(idx1, idx2) {
        [this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
    }

    getParentIdx(idx) {
        return Math.floor((idx - 1) / 2);
    }
    getLeftIdx(idx) {
        return idx * 2 + 1;
    }
    getRightIdx(idx) {
        return idx * 2 + 2;
    }

    push(value) {
        this.heap.push(value);
        this.bubbleUp();
    }

    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        if (this.heap.length === 0) return [null, null];

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();

        return min;
    }

    bubbleUp() {
        let currIdx = this.size() - 1;
        let parentIdx = this.getParentIdx(currIdx);

        // 노드의 구성이 [요청 시간, 실행 시간]이므로 1번 인덱스인 실행 시간을 비교
        while (currIdx > 0 && this.heap[currIdx][1] < this.heap[parentIdx][1]) {
            this.swap(currIdx, parentIdx);
            currIdx = parentIdx;
            parentIdx = this.getParentIdx(currIdx);
        }
    }

    bubbleDown() {
        let currIdx = 0;
        let leftIdx = this.getLeftIdx(currIdx);
        let rightIdx = this.getRightIdx(currIdx);

        while (
            (leftIdx < this.size() &&
                this.heap[leftIdx][1] < this.heap[currIdx][1]) ||
            (rightIdx < this.size() &&
                this.heap[rightIdx][1] < this.heap[currIdx][1])
        ) {
            const smallerIdx =
                rightIdx >= this.size() ||
                this.heap[leftIdx][1] < this.heap[rightIdx][1]
                    ? leftIdx
                    : rightIdx;

            this.swap(currIdx, smallerIdx);
            currIdx = smallerIdx;
            leftIdx = this.getLeftIdx(currIdx);
            rightIdx = this.getRightIdx(currIdx);
        }
    }
}

function solution(jobs) {
    const jobsHeap = new MinHeap();
    let timeLapsed = 0; // 현재 시간
    let timeSum = 0; // 누적 요청 후 종료까지 걸린 시간 
    let jobIdx = 0; // jobs 순회용 인덱스

    // 현재 시간 이전에 요청된 프로세스만 힙에 push하도록 요청시간을 기준으로 오름차순 정렬 
    jobs.sort((a, b) => a[0] - b[0]);
    while (jobIdx < jobs.length || jobsHeap.size()) {
        // 현재 시간 이전에 요청된 프로세스를 힙에 posh
        while (jobIdx < jobs.length && jobs[jobIdx][0] <= timeLapsed) {
            jobsHeap.push(jobs[jobIdx]);
            jobIdx++;
        }

        // 수행 시간이 최소인 프로세스를 pop
        const [startTime, processTime] = jobsHeap.pop();
        // 프로세스가 pop된 경우
        if (processTime) {
            // 누적 시간과 현재 시간을 업데이트 
            timeSum += timeLapsed - startTime + processTime;
            timeLapsed += processTime;
        // 수행할 프로세스가 없는 경우
        } else {
            // 현재 시간을 증가
            timeLapsed++;
        }
    }

    // 누적 시간을 프로세스 수로 나누어 평균 시간을 반환
    return Math.floor(timeSum / jobs.length);
}