[프로그래머스] Lv.3 디스크 컨트롤러 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42627
• 힙(heap)
  • 🔑 현재 시간에 작업할 수 있는 작업들 중 소요 시간이 적은 작업을 찾기
  • 🔑 현재 시간에 작업할 수 있는 작업이 없으면 먼저 들어온 요청 시간을 현재 시간으로 업데이트
  • 🔑 우선순위 큐인 heapq에 작업을 추가하면 소요 시간이 적은 작업 순으로 자동 정렬이 일어남

 

from heapq import *

def solution(jobs):
    
    # 정답, 처리한 작업 수, 현재 시간
    answer, cnt, time = 0, 0, 0
    heap = []   # 우선순위 큐
    
    jobs.sort() # 요청 시간 기준으로 오름차순 정렬
    
    while True:
        while cnt < len(jobs) and jobs[cnt][0] <= time:    # 현재 시간에 수행 가능한 요청 찾기
            heappush(heap, (jobs[cnt][1], jobs[cnt][0])) # 소요 시간을 앞에 넣으면 소요 시간 기준으로 오름차순 정렬됨
            cnt += 1
            
        if heap:
            x, y = heappop(heap)    # 소요 시간, 요청 시간
            time += x   # 현재 시간에 소요 시간 더하기
            answer += time - y  # 소요 시간을 더한 현재 시간 - 요청 시간을 정답에 증가
        elif cnt == len(jobs):  # 모든 작업을 처리했으면 끝
            break            
        else:
            time = jobs[cnt][0] # 현재 시간에 수행할 수 있는 작업이 없으면 먼저 들어온 요청 시간을 현재 시간으로 설정
        
    return answer // len(jobs)