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

1. 문제

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

 

2. 코드

python 1

from heapq import heappush as push, heappop as pop

def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1
    heap = []
    
    while i < len(jobs):
        for job in jobs:
            if start < job[0] <= now:
                push(heap, job[::-1])
        
        if len(heap) > 0:
            cur = pop(heap)
            start = now
            now += cur[0]
            answer += now - cur[1]
            i += 1
        else:
            now += 1
            
    return answer // len(jobs)

풀이

1. answer - 작업시간의 총합, heap - 우선 큐 담당 배열
2. now - 현재시점, start - 시작시점
3. 현재 시점까지 도착한 작업들을 heap에 추가 → 가장 짧은 처리시간을 가진 작업을 우선함
4. 현재 작업 중일때
   1. 가장짧은 처리시간을 가진 작업 꺼냄
   2. start를 now로 변경
   3. now를 현재 처리시간을 더해서 변경함
   4. answer = 작업완료시간 - 도착시간
5. 작업이 없으면 → 시간증가해서 도착시간이 되게 함

 

python 2

import heapq
from collections import deque

def solution(jobs):
    tasks = deque(sorted([(x[1], x[0]) for x in jobs], key=lambda x: (x[1], x[0])))
    q = []
    heapq.heappush(q, tasks.popleft())
    current_time, total_response_time = 0, 0
    while len(q) > 0:
        dur, arr = heapq.heappop(q)
        current_time = max(current_time + dur, arr + dur)
        total_response_time += current_time - arr
        while len(tasks) > 0 and tasks[0][1] <= current_time:
            heapq.heappush(q, tasks.popleft())
        if len(tasks) > 0 and len(q) == 0:
            heapq.heappush(q, tasks.popleft())
    return total_response_time // len(jobs)

 

3. 메모

• heapq로 가장 작은 값을 빠르게 꺼낼 수 있어서 사용함
• python 2가 속도가 더 빠름
• 나는 heapq 사용까지만 생각함(python 1)