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

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

 

문제 요약

각 작업의 [작업 요청 시점, 작업 소요시간]이 주어질 때
요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리 시, 처리 시간의 평균값?

 

코드 설명

import heapq
def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1
    heap = []
    
    while i < len(jobs):
        # 현재 시점에서 처리할 수 있는 작업을 heap에 저장
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
            
        # 처리할 작업이 있는 경우
        if len(heap) > 0:
            cur = heapq.heappop(heap)
            start = now
            now += cur[0]
            answer += now - cur[1]
            i += 1
            
        else:
            now += 1
    
    
    return answer // len(jobs)

 

대기 시간이 짧아야 하기 때문에, 현재 시점에서 매번 처리할 수 있는 작업 중 가장 짧은 것을 선택하기 위해

작업 소요시간을 기준으로 정렬될 수 있게 구현했다.

 

heap의 길이가 0보다 크면, 처리할 작업이 있는 경우이므로

작업 요청 시간과 종료 시간을 계산하고 다음 작업으로 넘어갈 수 있도록 start, now 값을 갱신해준다.

 

heap 길이가 0이면, 다음 시간으로 넘어가준다.

 

배운 점

- 힙(우선순위 큐)는 작업의 우선순위를 효율적으로 관리할 수 있는 자료구조이다.

- 작업이 없는 경우에도 시간을 흘려보내야 한다.

 

참고 자료

https://soohyun6879.tistory.com/136