[Chapter16] - 힙으로 우선순위 유지하기

[lee-ji-hoon]

https://school.programmers.co.kr/learn/courses/30/lessons/42627?language=kotlin

class Solution {
    
    fun solution(jobs: Array<IntArray>): Int {
        // (작업번호, 요청시각, 소요시간) 형태로 변환 후 요청 시각으로 정렬
        val indexedJobs = jobs.mapIndexed { index, job ->
            Triple(index, job[0], job[1])
        }.sortedBy { it.second }

        // 우선순위 큐: 소요시간 짧은 것 > 요청시각 빠른 것 > 작업번호 작은 것 순
        val pq = PriorityQueue<Triple<Int, Int, Int>>(
            compareBy({ it.third }, { it.second }, { it.first })
        ) // Triple(작업번호, 요청시각, 소요시간)

        var currentTime = 0
        var totalTurnaroundTime = 0
        var jobIndex = 0
        var completedJobs = 0

        while (completedJobs < jobs.size) {
            // 현재 시각 이전에 요청된 작업들을 대기 큐에 추가
            while (jobIndex < indexedJobs.size && indexedJobs[jobIndex].second <= currentTime) {
                val (idx, reqTime, duration) = indexedJobs[jobIndex]
                pq.offer(Triple(idx, reqTime, duration))
                jobIndex++
            }

            if (pq.isNotEmpty()) {
                // 우선순위가 높은 작업 선택 및 처리
                val (_, requestTime, duration) = pq.poll()
                currentTime += duration
                totalTurnaroundTime += currentTime - requestTime
                completedJobs++
            } else {
                // 대기 큐가 비어있으면 다음 작업 요청 시각으로 이동
                if (jobIndex < indexedJobs.size) {
                    currentTime = indexedJobs[jobIndex].second
                }
            }
        }

        return totalTurnaroundTime / jobs.size
    }
}

graph TB
    Start([시작]) --> Init[초기화<br/>현재시각 = 0<br/>완료작업 = 0]
    Init --> Sort[작업들을 요청시각 순으로 정렬]
    Sort --> Loop{모든 작업<br/>완료?}

    Loop -->|No| AddJobs[현재 시각까지 요청된<br/>작업들을 Heap에 추가]
    AddJobs --> CheckHeap{Heap이<br/>비어있나?}

    CheckHeap -->|No| PopHeap[Heap에서 최우선 작업 꺼내기<br/>소요시간 가장 짧은 것]
    PopHeap --> Process[작업 처리<br/>currentTime += duration<br/>반환시간 누적]
    Process --> Loop

    CheckHeap -->|Yes| TimeJump[다음 작업 요청 시각으로<br/>시간 이동]
    TimeJump --> Loop

    Loop -->|Yes| Calc[평균 반환 시간 계산]
    Calc --> End([종료])

    style Start fill:#e1f5e1
    style End fill:#ffe1e1
    style PopHeap fill:#fff4e1
    style Process fill:#e1f0ff

Loading

Heap의 장점

graph LR
    A[대기 중인 작업들] --> B{어떤 작업을<br/>먼저 처리?}
    B --> C[Heap 사용]
    C --> D[O log n 삽입/삭제]
    D --> E[효율적인 우선순위 관리]

    B --> F[배열 사용]
    F --> G[O n 삽입/삭제]
    G --> H[비효율적]

    style C fill:#e1f5e1
    style D fill:#e1f5e1
    style E fill:#e1f5e1
    style F fill:#ffe1e1
    style G fill:#ffe1e1
    style H fill:#ffe1e1

Loading