[프로그래머스/힙(Heap)/2] 디스크 컨트롤러 (JS)

출처: 프로그래머스 코딩테스트 디스크 컨트롤러(Heap) 2번째 문제
(https://programmers.co.kr/learn/courses/30/lessons/42627)

문제 설명

이번 문제는 그림 예시가 많아 생략
주소참고 바람

제한사항

• jobs의 길이는 1 이상 500 이하입니다.
• jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

풀이 방법

1. 우선순위큐를 생성한다(작업들이 들어갈 예정)
2. 반복문 시작
3. 기본적으로 time 변수를 0으로 초기화 해두고 반복문 안에서 1씩 증가시킨다.
4. 먼저 현재 시간에 들어 올 작업들을 큐에 삽입한다. 이렇게 되면 우선순위가 작업이 짧은 순으로 배치되게 된다.
5. 큐에 작업이 있지만 isProcess가 false일때 즉 작업이 진행중이 아닐때는 큐에서 작업을 빼내어 작업을 진행하게 된다.
6. 작업을 진행할때는 들어온 시작과 완료시간을 삽입하고 isProcess를 true로 바꿔 작업이 진행중임을 알린다.
7. 만약 time이 successTime과 일치하면 즉 작업이 완료되면 평균시간을 endProcess 배열에 삽입하고 isProcess를 false로 바꿔 작업이 끝났음을 알린다.
8. 만약 endProcess 배열에 크기가 작업 배열의 크기와 같아지면 모든 작업이 끝난 것임으로 반복문을 종료한다.
9. endProcess에 담긴 평균시간들의 평균을 계산하여 결과를 반환한다.

소스 코드

function solution(jobs) {
    const jobSize = jobs.length
    const PQ = new PriorityQueue()
    let time = 0
    let enterTime = 0
    let successTime = 0
    let isProcess = false
    const endProcess = []
    while (endProcess.length < jobSize) {
        // 현재 시간에 들어 올 작업들을 큐에 삽입
        const pushList = jobs.filter((job) => job[0] === time)
        for (const el of pushList) {
            PQ.push({ enterTime: el[0], processTime: el[1] })
        }
        // 작업이 완료 되었을 때
        if (time !== 0 && time === successTime) {
            endProcess.push(successTime - enterTime) //완료 배열에 (작업끝난 시간 - 큐에 등록된 시간) = 작업이 진행된 시간 을 삽입
            isProcess = false // 현재 작업이 없음을 알림
        }
        // 현재 작업이 없을 때 다음 작업을 시작
        if (PQ.queue.length !== 1 && isProcess === false) {
            const popElement = PQ.pop() // 큐에서 새로운 작업을 빼낸다
            enterTime = popElement.enterTime // 그 작업에 등록 시간 할당
            successTime = time + popElement.processTime // 끝나는 시간 할당
            isProcess = true // 현재 작업이 진행중임을 알림
        }
        time++ // 시간초 증가
    }
    // 끝난 작업들의 진행시간의 평균시간을 계산 후 결과 반환
    return Math.trunc(endProcess.reduce((acc, cur) => acc + cur, 0) / endProcess.length)
}

class PriorityQueue {
    constructor(fn) {
        this.queue = [null]
    }
    push(element) {
        const queue = this.queue
        queue.push(element)
        const queueSize = queue.length
        if (queueSize === 2) {
            return
        }
        let currentIdx = queueSize - 1
        let parentIdx
        while (currentIdx > 1) {
            parentIdx = Math.trunc(currentIdx / 2)
            if (queue[currentIdx].processTime > queue[parentIdx].processTime) {
                break
            }
            this.swap(queue, currentIdx, parentIdx)
            currentIdx = parentIdx
        }
    }

    pop() {
        const queue = this.queue
        const queueSize = queue.length
        if (queueSize === 2) {
            return queue.pop()
        }
        this.swap(queue, 1, queueSize - 1)
        const popData = queue.pop()
        let currentIdx = 1
        while (currentIdx < queueSize) {
            const result = this.check(queue, currentIdx)
            if (result === null) {
                break
            }
            if (queue[currentIdx].processTime <= queue[result].processTime) {
                break
            }
            this.swap(queue, currentIdx, result)
            currentIdx = result
        }
        return popData
    }

    check(queue, idx) {
        const leftChildIdx = idx * 2
        const rightChildIdx = idx * 2 + 1
        if (!queue[leftChildIdx]) {
            return null
        } else if (!queue[rightChildIdx]) {
            return leftChildIdx
        }
        return queue[leftChildIdx].processTime < queue[rightChildIdx].processTime ? leftChildIdx : rightChildIdx
    }
    swap(queue, i, j) {
        ;[queue[i], queue[j]] = [queue[j], queue[i]]
    }
    display() {
        console.log(this.queue)
    }
}

후기

우선순위 큐를 자바스크립트로 직접 코딩해봤는데 이론으로 배울때는 금방 이해됐지만 실제로 머리속에 있는 지식을 코딩하는 것은 쉽지 않아 구글에서 c++예제를 많이 참고한 것 같다. 내 머리속에 있는 지식을 원하는대로 코딩할 수 있는 사람이 되고 싶다.