[프로그래머스] 디스크 컨트롤러 (level3, python)

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

프로그래머스

 

아이디어

최소힙을 사용하여 푸는 문제였다.

 

for time, job in jobs:
    if start < time <= now:
        heapq.heappush(heap, (job, time))

jobs를 순회하면서 start와 now 사이(이전 작업의 시작-끝 범위)에 시작하는 job을 찾아 최소힙에 넣는다.

이때 job을 기준으로 정렬되어야 하기 때문에 job과 time의 위치를 바꿔 넣는다.

 

if len(heap) > 0:
    job_tmp, time_tmp = heapq.heappop(heap)
    start = now
    now += job_tmp 
    answer += (now - time_tmp) 
    i += 1
    continue
now += 1

 

만약 heap에 값이 있다면,

heap에 있는 값을 꺼낸다.

start를 현재 시간(now)으로 초기화 해준다.

now에 job을 더해서 작업이 완료된 시간을 구한다.

answer에 전체 시간(작업이 완료된 시간 - 호출된 시간)을 더한다.

 

만약 heap에 값이 없다면 현재시간에 +1 해준다.

 

jobs = [[0, 3], [1, 9], [2, 6]]

위 예시를 넣어서 생각해보자.

start	now	heap(heappop되는 요소 bold)	answer
-1	0	[3, 0]	3
0	3	[6, 2], [9, 1]	10
3	9	[9, 1]	27
9	18

 

이런 과정을 거치게 된다.

이후 return answer // len(jobs)에 의해서 27//3인 9가 return되는 것이다.

 

전체 코드

import heapq

def solution(jobs):
    start, now, i = -1, 0, 0
    answer = 0
    heap = []
    
    while i < len(jobs):
        for time, job in jobs:
            if start < time <= now:
                heapq.heappush(heap, (job, time))
        
        if len(heap) > 0:
            job_tmp, time_tmp = heapq.heappop(heap)
            start = now
            now += job_tmp 
            answer += (now - time_tmp) 
            i += 1
            continue
        now += 1
        
    return answer // len(jobs)