프로그래머스 Lv.3 디스크 컨트롤러 파이썬(Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42627?itm_content=course14743

 

풀이

문제에 앞서 요청이 들어온 순서대로 처리한다면 어떤 코드를 짜야 할까?

각 job의 원소는 [call, spend]로 구성된다.

call: 요청시작 시간

spend: 소요 시간

각 작업의 현재 시간(now) += 작업의 소요 시간(spend)

요청부터 종료까지 걸린 시간 = now - call

이를 이용하면 다음의 코드를 구할 수 있다.

def solution(jobs):
    answer = 0
    now = 0
    
    realSpends = []
    for call, spend in jobs:
        now += spend
        realSpend = now - call
        realSpends.append(realSpend)
    
    answer = sum(realSpends) / len(realSpends)
    return answer

 

근데 어떤 순서로 처리해야 작업의 요청부터 종료까지 걸린 시간의 평균이 최소가 되도록 할까?

이를 위해 Heap을 이용해 작업시간의 최소를 실시간으로 업데이터해가며 구했다.

작업의 소요시간이 작은 순서대로 요청을 처리해준다.

전체 코드

import heapq
def solution(jobs):
    answer = 0
    now = 0
    i = 0
    start = -1
    heap = []
    realSpends = []
    
    while i < len(jobs):
        for call, spend in jobs:
            if start < call <= now:
                heapq.heappush(heap,[spend,call])
        if heap:
            current = heapq.heappop(heap)
            start = now
            now += current[0]
            realSpends.append(now - current[1])
            i += 1
        else:
            now += 1
            
    answer = sum(realSpends)// len(realSpends)
    return answer