[프로그래머스 자바스크립트] ‘디스크 컨트롤러’ 풀기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

---

1. 생각

우선순위 큐(즉, Heap)을 사용해서 풀어야 하는 문제다. Javascript는 우선순위 큐를 직접 구현해야하는데, 아직 다 외우지 못해서 아래 블로그 글을 참고해서 우선순위 큐를 구현했다.

(블로그 링크: https://velog.io/@qltkd5959/JS )

 

작업의 우선순위는

1. 작업의 소요시간이 짧은 것,
2. 작업의 요청 시각이 빠른 것
3. 작업의 번호가 작은 것

이다.

 

이 문제에서 주어지는 jobs는 [작업이 요청되는 시점, 작업의 소요시간] 배열이다. 작업 번호가 부여되지 않았으니 새로 jobsQueue를 만

들고 작업 번호를 부여하였다.

 

그리고 작업 요청 시간순으로 한 번 sort를 하였고, 그리고 아까 구현한 MaxHeap(waitingQueue)을 사용하여 우선순위들을 나열해야한다.

 

현재 시점까지 요청된 작업을 대기 큐에 추가하고, 대기 큐가 비어있으면 다음 작업 요청 시점으로 이동한다. 우선 순위가 가장 높은 작업을 선택해서 이 작업을 활용해서 작업 완료 시점과 반환 시간을 계산한다. 이 작업을 모든 작업이 끝날 때까지 계속 반복한다.

---

2. 코드

function solution(jobs) {    
    // jobs = [작업이 요청되는 시점, 작업의 소요시간]

    // 1. 작업의 소요시간이 짧은 순으로 나열
    // 2. 작업의 요청 시간이 빠른 순으로 나열
    // 3. 작업 번호가 낮은 순으로 정렬


    // 새로운 jobsQueue를 만들고 작업 번호를 부여
    const jobsQueue = [];
    for(let i = 0; i < jobs.length; i++) {
        jobsQueue.push({
            jobNum: i,
            requestTime: jobs[i][0],
            durationTime: jobs[i][1],

        })
    }

    // 작업 요청 시간 순으로 나열
    jobsQueue.sort((a,b) => a.requestTime - b.requestTime);

    let currentTime = 0;
    let totalTurnAroundTime = 0;
    let completedJobs = 0;

    const waitingQueue = new MaxHeap();

    while(completedJobs < jobs.length) {

        // 현재 시점까지 요청된 작업을 대기 큐에 추가
        while(jobsQueue.length > 0 && jobsQueue[0].requestTime <= currentTime) {
            waitingQueue.heap_push(jobsQueue.shift());
        }

        // 대기 큐가 비어있으면 다음 작업 요청 시점으로 이동
        if(waitingQueue.isEmpty()) {
            if(jobsQueue.length > 0) {
                currentTime = jobsQueue[0].requestTime;
                continue;
            }
            else {
                break;
            }
        }

        // 우선순위가 가장 높은 작업 선택
        const job = waitingQueue.heap_pop();

        // 작업 완료 시점 계산
        const completionTime = currentTime + job.durationTime;

        // 반환 시간 계산
        const turnAroundTime = completionTime - job.requestTime;

        totalTurnAroundTime += turnAroundTime;
        currentTime = completionTime;
        completedJobs++;
    }

    return Math.floor(totalTurnAroundTime / jobs.length);
}

// 최대 힙
class MaxHeap {
    constructor() {
        this.heap = [null];
    }

    isEmpty() {
        return this.heap.length <= 1;
    }

    compare(a, b) {
        if(a.durationTime !== b.durationTime) {
            return a.durationTime > b.durationTime;
        }

        if(a.requestTime !== b.requestTime) {
            return a.requestTime > b.requestTime;
        }

        return a.jobNum > b.jobNum;
    }

    heap_push(value) {
        this.heap.push(value);
        let currentIndex = this.heap.length - 1;
        let parentIndex = Math.floor(currentIndex / 2);

        while (parentIndex !== 0 && this.compare(this.heap[parentIndex], value)) {
            const temp = this.heap[parentIndex];
            this.heap[parentIndex] = this.heap[currentIndex];
            this.heap[currentIndex] = temp;
            currentIndex = parentIndex;
            parentIndex = Math.floor(currentIndex / 2);
        }
    }

    heap_pop() {
        if(this.heap.length === 2) return this.heap.pop();

        let returnValue = this.heap[1];
        this.heap[1] = this.heap.pop();
        let currentIndex = 1;
        let leftIndex = 2;
        let rightIndex = 3;
        while(
            (leftIndex < this.heap.length && this.compare(this.heap[currentIndex], this.heap[leftIndex])) ||
            (rightIndex < this.heap.length && this.compare(this.heap[currentIndex], this.heap[rightIndex]))
        ) {
            const temp = this.heap[currentIndex];

            if(rightIndex >= this.heap.length || 
               (leftIndex < this.heap.length && this.compare(this.heap[rightIndex], this.heap[leftIndex]))) {
                this.heap[currentIndex] = this.heap[leftIndex];
                this.heap[leftIndex] = temp;
                currentIndex = leftIndex;
            } else {
                this.heap[currentIndex] = this.heap[rightIndex];
                this.heap[rightIndex] = temp;
                currentIndex = rightIndex;
            }

            leftIndex = currentIndex * 2;
            rightIndex = leftIndex + 1;
    }
        return returnValue;
}
    heap_return() {
        return this.heap;
    }
}

 

---

이번에는 내 힘으로 못 풀고 AI의 도움을 받았다.

우선순위 큐 문제만 풀려고하면 머릿속이 복잡해지는데, 계속 문제와 맞닥뜨리면서 익숙해져야겠다.