[프로그래머스/Python] - Lv3 / 디스크 컨트롤러

문제

하드디스크는 한번에 하나의 작업만 수행.
각 작업의 (요청시점, 처리시간) 리스트로 주어짐
작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하여
평균 구하기

내 코드

import heapq
def solution(jobs):
    # 하드디스크는 한 번에 하나의 작업만 수행.
    # 각 작업의 (요청 시점, 처리 시간) 리스트로
    # 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하기.
    n = len(jobs)
    data = jobs
    heap = []
    for i in range(n):
        heapq.heappush(heap, (data[i][0], data[i][1]))
    temp = []
    last = 0 # 가장 마지막 작업의 끝나는 시간 
    res = 0
    
    # 애초에 요청시각 빠른 순으로 들어가 있음. 
    while heap:
        while heap and heap[0][0] <= last:
            start, time = heapq.heappop(heap)
            heapq.heappush(temp, (time, start))
        
        if temp: # 가능한 경우 존재
            time, start = heapq.heappop(temp)
            res += last - start +  time
            last += time
        else:
            start, time = heapq.heappop(heap)
            res += time
            last = start + time
        
        while temp:
            time, start = heapq.heappop(temp)
            heapq.heappush(heap, (start, time))
    
    res = int(res/n)
    return res

코멘트

굉장히 오래 걸렸다.. 문제를 잘못 이해해서...
일단 각 작업의 요청시각 기준으로 먼저 오름차순 했어야 했다.
그 후 현재 시점에서 마지막 작업의 끝나는시간보다 요청 시각이 같거나 작은 애들이 다음 작업으로 올 수 있으므로 큐에 (처리시간, 요청시각)을 우선순위로 넣었어야 했다.

근데 내가 여기서 실수한게 따로 대기시간 + 처리시간을 개산해서 우선순위 큐에 넣었다.
heap에서 작업을 꺼내서 temp에 추가할 때 (처리시간, 요청시각)으로 넣어주고 있다. 이렇게 하면 처리시간을 기준으로 최소힙을 유지한다.

SJF 스케줄링 방식인데.. 작업을 요청시점 기준으로 이미 오름차순 정렬했잖아. 현재 가능한 작업 중에서 처리 시간이 가장 짧은 작업을 선택만 하면 된다 !

직관적으로 생각해도, 처리시간이 짧아야 이후에 계속 대기시간이 짧다. 이걸 생각하느라고..!!! ㅠ

요청시각이 오름차순으로 정렬된 상태에서, 처리시간이 짧은 걸 처리하는 것이 대기시간 + 처리시간이 작은 것을 처리하는 것이다.

코드 최적화

import heapq
def solution(jobs):
    # 하드디스크는 한 번에 하나의 작업만 수행.
    # 각 작업의 (요청 시점, 처리 시간) 리스트로
    # 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하기.
    n = len(jobs)
    data = jobs
    heap = []
    for i in range(n):
        heapq.heappush(heap, (data[i][0], data[i][1]))
    temp = []
    last = 0 # 가장 마지막 작업의 끝나는 시간 
    res = 0
    
    # 애초에 요청시각 빠른 순으로 들어가 있음. 
    while heap or temp:
        while heap and heap[0][0] <= last:
            start, time = heapq.heappop(heap)
            heapq.heappush(temp, (time, start))
        
        if temp: # 가능한 경우 존재
            time, start = heapq.heappop(temp)
            res += last - start +  time
            last += time
        else:
            start, time = heapq.heappop(heap)
            res += time
            last = start + time
        
        
    
    res = int(res/n)
    return res

매번 temp를 꺼내서 heap에 넣을 필요가 없었다. 계속 유지하면서 그냥 종료조건만 heap, temp 모두 다 비워졌을 때로 바꾸면 깔끔하게 해결할 수 있다.