[Python - 프로그래머스] 힙(Heap) > 디스크 컨트롤러

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

 

---

 

Solution

 

import heapq
import numpy as np
 
def solution(jobs):
    time1 = heapq.nlargest(len(jobs), jobs, key=lambda x: (x[0], x[1])) # 작업 요청 시점으로 sorting
    time2 = heapq.nlargest(len(jobs), jobs, key=lambda x: (x[1], x[0])) # 작업 소요 시간으로 sorting
    
    now = list() # 현재 시간
    
    # 가장 먼저 요청한 작업
    answer = list()
    m = time1.pop()
    time2.remove(m)
    answer.append(m)
    now.append(m[1] + m[0])
    
    # now보다 요청 시간이 적은 것들 중에서 작업 소요시간이 작은 것
    while len(time1) > 0 :
        for i in range(len(time2)-1,-1,-1) :
            if time2[i][0] <= now[-1] : 
                break
        if (i == 0) & (time1[0][0] > now[-1]) : # 만약 now보다 요청 시간이 적은게 없다면
            m = time2.pop()
            now.append(m[0] + m[1])
        else :
            m = time2.pop(i)
            now.append(now[-1] + m[1])
 
        time1.remove(m)
        answer.append(m)
        
    mea = [now[i]-answer[i][0] for i in range(len(answer))]
    return int(sum(mea)/len(mea))

 

작업 소요 시간이 더 적은 것들부터 처리하면 된다.

먼저 heap으로 작업 요청 시점을 기준으로 sorting, 작업 소요 시간을 기준으로 sorting한다.

단, 동일한 시점에 두개 이상의 작업이 들어 올 수도 있으므로 lambda x : (x[0], x[1]) 로, 동일 시간 일 때는 소요 시간을 기준으로 sorting할 수 있도록 했다.

 

now에는 매 작업을 할 때마다 현재 시점을 저장한다.

 

이후 가장 먼저 요청한 작업을 처리한다.

다음은 현재 시점(now[-1])보다 요청 시점이 더 먼저인 것들 중 작업 소요 시간이 가장 적은 것을 answer에 저장한다.

(이렇게 처리 순서대로 answer에 저장해놓고 마지막에 한 번에 평균 소요 시간을 계산한다.)

 

현재 시점보다 요청 시간이 더 뒤에 있을 수도 있으므로 그런 것들도 고려한다.

ex) [[0, 1], [1, 1], [50, 7]] -> 3

 

마지막으로 now에서 answer에 저장된 소요시간을 순서대로 빼주면 각 작업별로 소요시간이 나온다.

이걸 평균내어 return하면된다.

단, 소수점 아래는 버리므로 이를 주의한다.