[프로그래머스 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