[Python] 디스크 컨트롤

1. 문제

 

 

 

2. 풀이 과정

방법 1)

import heapq as hq
def solution(jobs):
    answer = 0
    jobs.sort()
    
    heap = []
    count = 0 #시간
    pre_idx = -1
    while True:
    	#전에 heap에 안들어갔었고, 현재 count보다 작은 값 heap에 넣기
        temp = pre_idx
        for i in range(temp+1, len(jobs)):
            if jobs[i][0] > count:
                break
            hq.heappush(heap, [jobs[i][1], jobs[i][0]])
            pre_idx = i
            
        if heap:
            e = hq.heappop(heap)
            count += e[0] #요청 처리 끝낸 후
            answer += count - e[1] #현재 시각 - 요청 들어온 시간
        else:
        	#heap에도 없고, jobs도 끝까지 다 읽었으니 종료
            if pre_idx == len(jobs)-1:
                break
            #heap에 없으면 시간 1증가
            count += 1
        
    return answer//len(jobs)

 

방법 2) jobs를 읽은 위치를 저장하기 위해, idx를 따로 저장하는 대신 jobs를 deque를 이용해서 읽은 값은 빼버린다.

앞의 방법 1)보다 약 1.2배 빠르다.

import heapq as hq
from collections import deque
def solution(jobs):
    answer = 0
    l = len(jobs)
    #시작 위치를 key로 정렬하고, 큐에 넣을 때는 [(a[1], a[0])] 형식으로 위치를 바꿔 저장
    #위치를 바꾸는 이유 : min heap에 넣어서, 소요시간을 기준으로 정렬하기 위함
    jobs = deque(sorted([(a[1], a[0]) for a in jobs], key = lambda x:(x[1], x[0])))
    heap = []
    hq.heappush(heap, jobs.popleft())
    count = heap[0][1] #제일 처음 값의 요청이 들어온 시간으로 초기화
    
    while heap:
        dur, start= hq.heappop(heap)
        count += dur
        answer += count-start
        
        #현재 count를 기준으로 요청이 들어온 것들을 넣기
        while jobs and jobs[0][1] <= count:
            hq.heappush(heap, jobs.popleft())
        
        #heap은 비었고, 처리해야할 jobs 아직 남아있을 때 : count를 다음 요청까지 한번에 증가시키자
        if not heap and jobs:
            e = jobs.popleft()
            count = e[1]
            hq.heappush(heap, e)
    
    return answer//l