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

이 문제를 푸는데 핵심이 되는 것은 특정 시점에서 실행시킬 작업이 여러 가지일 때 어떤 것을 실행시킬지 선택하는 것이다.

 

예제에서 보면 알 수 있드시 작업시간이 짧은 작업을 먼저 처리할 때 평균 시간이 낮은 것을 알 수 있다.

 

운영체제 스케줄링 중 SJF(Shortest Job First)와 로직이 동일한 것으로 보인다.

 

무튼, 우리가 이 문제를 풀기 위해서 핸들링 해야하는 포인트는 2가지이다.

 

1. 어떤 Job이 남았는가?

2. 지금 내가 실행시킬 수 있는 Job은 무엇인가?

 

우리는 시간을 카운팅 하면서 남아있는 Job 중 실행할 수 있는 Job을 가져오기 위해 이 문제 유형인 힙(priority queue)를 사용할 것이다.

 

왜냐면 priority Queue를 사용하면 특정 값으로 정렬된 순서대로 값을 받아올 수 있기 때문이다!

 

그래서 시간이 빠른 순서대로 Queue에서 값을 받아오고자 한다.

 

만약 Priority Queue를 사용하지 않으면 매번 남은 요소 모든 것을 Search 해야한다.

 

Priority Queue를 사용해서 앞에서부터 현재 시간과 비교하며 수행할 수 있는 Job을 가져온다.

 

그리고 해당 Job들 중 가장 작업 시간이 짧은 것을 가져오기 위해서 여기서도 Priority Queue를 사용하고자 한다.

 

작업을 수행한 Job을 제외하고는 다시 맨처음 Queue에 집어넣어서 다시 정렬해준다.

 

물론 다시 안넣어주고 유지하다가 다음 Job 선택시에 사용해도 된다!

 

- 정리 -

1. 대기 중인 Job을 가진 Priority Queue인 waittingQueue에 모든 Job을 넣는다.

* 이때 시작 시간을 기준으로 정렬해준다

 

2. 이후 현재 시간에 수행할 수 있는 Job을 readyQueue에 넣어주고 작업시간을 기준으로 정렬해준다,

 

3. 가장 readyQueue의 가장 앞에 있는 것이 현재 수행할 수 있는 것 중 가장 빨리 끝나는 Job이므로 수행해준다.

 

4. 모든 Job을 수행할 때까지 계속 반복한다.

 

 

- 코드 -

 

import java.util.*

class Solution {
    fun solution(jobs: Array<IntArray>): Int {
        var answer = 0
        var time = 0
        var waittingQueue = PriorityQueue<Job>(compareBy({it.start}))


        for(i in 0..jobs.size-1){
            var job = Job(jobs[i][0],jobs[i][1])
            waittingQueue.offer(job)
        }

        while(!waittingQueue.isEmpty()){
            var readyQueue = PriorityQueue<Job>(compareBy { it.during })
            while(!waittingQueue.isEmpty() && time>=waittingQueue.peek().start){
                readyQueue.offer(waittingQueue.poll())
            }
            if(readyQueue.isEmpty()){
                time++
                continue
            }
            time += readyQueue.peek().during
            answer += time - readyQueue.peek().start
            readyQueue.poll()

            for(i in 0..readyQueue.size-1){
                waittingQueue.offer(readyQueue.poll())
            }
        }

        answer /= jobs.size

        return answer
    }
}

data class Job(
    var start:Int = 0,
    var during:Int = 0
)