[힙 python] 프로그래머스 디스크 컨드롤러

레벨3

 

 

풀이방법 1

def solution(jobs):
    answer = 0
    now, start,i = 0,-1,0
    heap = []
    # 모든 작업을 할 때까지 반복
    while i < len(jobs):
        # start 부터 now 시간까지에 들어 있는 모든 작업들을 heap에 heappush
        for job in jobs:
            if start < job[0] <= now :
                heapq.heappush(heap,[job[1], job[0]]) # 작업 시간(job[0])을 비교해야 하므로 0번에 삽입
        # heap 에 있는 작업시간이 낮은 것부터 heappop()
        if len(heap) != 0 :
            dur, s = heapq.heappop(heap)
            start = now
            now = max(s+dur, now+dur) # 요청 시간과 현재 시간의 max 값을 비교
            answer += now - s
            i+=1
            print(now,s)
        # heap에 아무것도 없을 경우 1씩 증가
        elif len(heap) ==0:
            now += 1
    return answer // len(jobs)

 

 

 

 

풀이방법 1과 유사하지만 jobs에서 데이터 자체를 heappop하는 것도 가능하다. 

풀이방법 2

import heapq
def solution(jobs):
    answer = 0
    num = len(jobs)
    heapq.heapify(jobs)
    start, now,i = 0,0,0
    heap = []

    while i<num:
        while len(jobs)!=0 and jobs[0][0] <= now :
            s,t=heapq.heappop(jobs)
            heapq.heappush(heap,[t,s])
        if len(heap) != 0:
            dur, s = heapq.heappop(heap)
            now = max(s,now)+dur
            answer += (now-s)
            i+=1
        else:
            now+=1
    return answer//num