[프로그래머스 Lv.3] 디스크 컨트롤러 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

풀이

우선순위 큐를 활용하여 풀이한 문제이다. 현재 시간에서 처리할 수 있는 가장 소요시간이 적은 작업부터 우선적으로 우선순위 큐에서 꺼내 처리하게 하면, 최소의 평균 시간으로 전체 작업들을 처리할 수 있다.

 

먼저, 현재 시간까지 요청된 모든 작업들을 우선순위 큐에 넣는다. 다음으로 소요 시간이 가장 적은 작업부터 우선순위 큐에서 꺼내 처리를 진행한다. 만약 처리할 수 있는 작업이 없다면, 현재 시간을 +1씩 키운다.

위의 과정을 모든 작업들이 처리 완료될 때까지 반복한다.

 

문제를 풀이하면서 주의해야할 점은 "하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다."라는 제한 사항이다. 즉, 어떠한 작업도 수행하지 않고 대기하지는 말라는 것이다. 작업들의 조합에 따라서 아무것도 실행하지 않고 기다렸다가 실행하는 경우에 더 평균 수행 시간이 적은 경우도 있긴 한데 이런 복잡한 사항은 고려하지 않고 풀이해도 괜찮다는 것이다.

import heapq

def solution(jobs):
    answer, elapsed, cnt, limit = 0, 0, 0, -1 # 작업이 처리 완료될 때까지 걸린 시간들의 합, 현재 시간, 처리한 작업의 수, 이전까지의 작업들을 처리하는데 소요된 시간
    heap = []
    
    while cnt < len(jobs): # 모든 작업을 처리할 때까지 반복
        for job in jobs: # 모든 작업을 순회하며
            req, cost = job
            if limit < req <= elapsed: # 이전까지의 작업들을 처리하는데 소요된 시간과 현재 시간 사이에 요청된 작업이라면
                heapq.heappush(heap, [cost, req]) # 힙에 넣음
            
        if heap: # 힙이 비어있지 않다면
            cost, req = heapq.heappop(heap) # 우선순위 큐에서 cost가 가장 적은 것을 pop
            limit = elapsed # 현재 작업을 제외하고 이전까지의 작업들을 처리하는데 소요된 시간을 업데이트
            elapsed += cost # 작업을 처리하여, cost초만큼 현재 시간을 증가시킴
            answer += elapsed - req # 요청 시간부터 현재 시간까지 걸린 시간을 업데이트
            cnt += 1
        else: # 힙이 비었다면, 현재 처리할 수 있는 작업이 없는 경우이므로
            elapsed += 1 # 현재 시간을 1초 증가

    return answer // cnt