[프로그래머스] 디스크 컨트롤러 파이썬 풀이

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

프로그래머스

---

1. 풀이

• 현재 시간까지 요청된 모든 작업들 중에서 가장 작업 소요 시간이 짧은 것부터 처리하자 ➡ 최소 heap

heap에 요청된 작업을 모두 넣어두고 나서 한 개를 꺼내면, 바로 그것이 가장 짧은 소요 시간을 가지는 작업이다.

현재 시간 time에서 가장 짧은 작업의 작업 시간만큼 더해서 해당 작업이 처리됐음을 표현한자.

만약 현재 시간까지 요청된 작업이 없다면, 1초를 증가하고 다시 요청 작업이 있는지 확인하는 작업을 반복하자

 

 

 

2. 정답 코드

def solution(jobs):
    from heapq import heappush, heappop
    jobs.sort(reverse=True)
    n = len(jobs)
    turnaround = 0
    processed = 0
    time = 0
    candidate = []

    while processed < n:
        while jobs and jobs[-1][0] <= time:
            requested, duration = jobs.pop()
            heappush(candidate, (duration, requested))  # switch position
        
        if not candidate:
            time += 1
            continue
            
        current = heappop(candidate)
        time += current[0]
        turnaround += time - current[1]
        processed += 1
    
    return turnaround // n