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

문제링크

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

접근 방법

• 전체 시간을 최소화하기 위해서는 대기시간을 줄여야 한다. (소요시간은 줄일 수 없으므로)

• 대기하고있는 일들의 대기 시간을 줄이기 위해서는 수행시간이 적게 걸리는 일부터 해야한다.
  대기하고있는 일이 10개라 가정하면
  수행시간이 1인 일을 먼저 하면 나머지 9개의 일들은 누적해서 총 9초를 기다려야 하고, 수행시간이 3인 일을 먼저 하면 나머지 일들은 누적해서 총 27초를 기다려야 하기 때문이다.

• 따라서 대기하고 있는 일들을 담고, 소요시간이 적은 순서대로 일을 뽑아주는 우선순위 큐를 만들고, 큐가 빌때까지 실행한다.

코드 (python)

from heapq import *

def solution(jobs):
    length = len(jobs)
    heapify(jobs) # 요청시간 기준 우선순위 큐 [요청시간, 소요시간]
    q = [] # 대기하고있는 작업들, 소요시간 기준 우선순위 큐 [소요시간, 요청시간]
    total = 0 # 총 걸리는 시간

    # 이따 while문을 돌리기 위해 q에 시작값을 넣어준다.
    now = heappop(jobs)
    # start는 현재 하고있는 일이 끝나는 시간
    start = now[0] + now[1]
    total += now[1]
    # 일의 요청시간이 현재 일이 끝나는 시간보다 빠른 일들을 우선순위 큐에 담는다.
    # 즉, 지금 하고있는 일이 끝나면 바로 시작할 수 있는 일들
    while jobs and jobs[0][0] <= start:
        next = heappop(jobs)
        # 다음에 실행할 일은 소요시간이 빠른 순서로 뽑기 때문에 순서를 바꿔서 큐에 넣는다.
        heappush(q, (next[1], next[0]))

    # 만약 다음 일의 요청 시간이 start보다 늦어서 큐에 아무것도 넣지 못한 경우
    # 남아있는 일들중 가장 빨리 시작하는 일 하나를 큐에 넣는다.
    if not q and jobs:
        next = heappop(jobs)
        heappush(q, (next[1], next[0]))
	
    # 큐에서 하나씩 일을 빼면서, 큐가 빌때까지 반복한다.
    while q:
        cost, request = heappop(q)
        # 요청시간이 start보다 먼저인 일들은 대기시간이 있기 때문에
        # 대기시간 (start - request)를 전체 시간에 더해준다.
        if request <= start:
            total += (start - request) + cost
            start += cost
        # 요청시간이 start보다 늦어 바로 시작하는 일들은 처리시간만 더해준다.
        else:
            start = request + cost
            total += cost
		
        # 일을 하나 끝내면 start값이 바뀌므로 다시 큐에 일들을 집어넣는다.
        while jobs and jobs[0][0] <= start:
            next = heappop(jobs)
            heappush(q, (next[1], next[0]))

        if not q and jobs:
            next = heappop(jobs)
            heappush(q, (next[1], next[0])) 
	
    # 평균시간을 반환한다.
    return total // length