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

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42627

접근법

1. 현재 시간이 k ms 라면, 작업 시작시간이 k ms 이하인 작업들 중 가장 먼저 실행해야할 작업 ?

• 평균 소요시간을 낮추려면 현 시점에서 최대한 대기중인 작업들의 수를 낮춰야 한다.
• 이는 현재 가능한 작업들 중 제일 짧은 수행시간을 가진 작업을 우선 실행
• 이를 위해 k ms 이하인 작업들을 heapq에 넣고 수행시간을 기준으로 오름차순 정렬 -> heappush 할 때 tuple 형태로 (소요시간,작업) 넣는다면 소요시간 기준으로 정렬을 할 수 있다

2. 현재 시간이 k ms 이고, 대기 중인 작업들이 없을 수도 있다.
   ( 예를들어 현재 시간이 3 ms인데 제일 가까운 다음 작업 시작시간이 4ms인 경우 )

• 처음에 jobs를 오름차순으로 정렬하여 대기 중인 작업들 중 우선순위를 가릴 수 없는 경우 가장 가까운 다음 작업을 실행 ( 만약 시작시간이 같은 작업들이 여러개인 경우 소요시간이 가장 짧은 작업이 먼저 실행될 것 -> key=lambda x:(x[0],x[1]) )
• pq 에 다음 작업이 없는 경우 jobs[0]를 pq에 넣어주면 된다.

* heappush 정렬 팁과 2번 케이스를 고려해야 함.

코드

from heapq import heappush,heappop
def solution(jobs):
    answer = 0
    total_num = len(jobs)
    jobs.sort(key=lambda x:(x[0],x[1]))
    time = 0
    # 시작 Task
    pq = [(0,jobs.pop(0))]
    while( pq ):
        job = heappop(pq)[1]
        # 대기시간이 있는경우 와 없는 경우
        time = job[0] + job[1] if job[0] > time else time+job[1]
        answer += time - job[0]
        # 현재 수행하는 작업시간 안에 시작하는 작업들 추가
        while( jobs ):
            if( jobs[0][0] <= time or not pq):
                heappush(pq,(jobs[0][1],jobs.pop(0)))
            else:
                break
    return answer//total_num