디스크 컨트롤러 (lv3)

문제

코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

풀이

매 순간마다 현재 디스크가 유휴 상태인지, 아닌지 확인한 뒤, 유휴 상태라면 앞 순서의 요청부터 처리하고 아니라면 가장 작업 시간이 적게 소요되는 요청을 먼저 처리하도록 하는 문제이다. 매번 시간이 갱신 될 때마다, 현재 작업 중인 요청의 완료 시간보다 앞서 요청된 작업들은 대기열에 넣어놓는다. 만약 대기열이 비어있으면, 더이상 현재 시간까지는 아직 요청된 작업이 없다는 뜻이니 새로운 요청을 받아 수행한다. 당연히 비어있지 않다면 대기열에서 가장 작업 시간이 적은 요청을 처리하면 되겠다.

import heapq

def solution(jobs):
    length = len(jobs)
    
    # 큐 : 요청 순서대로 정렬하고, 동시 요청이면 비용이 적은 순으로 정렬
    # deque 사용 대신 list 역순 정렬
    jobs = sorted(jobs, key = lambda x : (-x[0],-x[1]))
    
    # 작업 처리 대기열 초기화
    pending = []

    sum_value = 0
    time = 0
    
    # 새로 요청되는 작업, 처리 대기 중인 작업 모두가 종료될 때 까지 반복
    while jobs or pending:
    	# 대기열이 비어있으면 새로운 요청 처리
        if not pending:
            idx,cost = jobs.pop()
            time = idx + cost
            sum_value += cost
        # 대기열이 차있으면, 대기 중인 작업 중 가장 비용이 적은 작업 처리
        else:
            cost,idx = heapq.heappop(pending)
            time += cost
            sum_value += time - idx
        
        # 현재 들어온 작업이 끝나는 시간까지, 새로 들어오는 작업은 전부 대기열에 삽입
        while jobs and jobs[-1][0] < time:
            i,v = jobs.pop()
            heapq.heappush(pending,(v,i))
            
    return sum_value//length