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

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

const 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)
    }
}