프로그래머스 알고리즘: 디스크 컨트롤러 (lv3)

https://school.programmers.co.kr/learn/courses/30/lessons/42627?language=python3#

from heapq import heapify, heappop, heappush

def solution(jobs):
    answer = 0
    sec = 0 # 현재 시각
    cnt_jobs = len(jobs)
    heapify(jobs)
    can_jobs = [] # 현재 시각 (sec) 에서 시작할 수 있는 작업들
    
    while jobs:
        try:
            while jobs[0][0] <= sec:
                idx, time = heappop(jobs)
                heappush(can_jobs, (time, idx))
        except:
            pass
        
        if not can_jobs: # 현재 시작할 수 있는 작업이 없음
            sec = jobs[0][0] # 다음 작업으로 시간 이동
            continue

        time, idx = heappop(can_jobs)
        answer += sec + time - idx
        sec += time
        
    while can_jobs:
        time, idx = heappop(can_jobs)
        answer += sec + time - idx
        sec += time
        
    return int(answer / cnt_jobs)

우선 핵심 아이디어인 현재 시점에서 실행할 수 있는 작업들 중 가장 실행 시간이 적은 작업을 선택한다 를 떠올려서 구현했으나, 거의 모든 테스트케이스에서 실패했다. 내가 실패한 이유는 다음과 같았다:

• can_jobs에서 현재 실행할 작업을 선택한 후, 나머지 작업들을 다시 jobs에 넣으려 함
  -> jobs는 작업이 요청되는 시점 을 기준으로 정렬되어 있고, can_jobs는 작업의 소요시간 을 기준으로 정렬되어 원소가 뒤바껴 있어 이를 다시 뒤집고 삽입했음

• 결과를 int로 변환하지 않았음 (...)

• 현재 시작할 수 있는 작업이 없는 경우를 생각 못했음

이를 고치고 실행하니 전체 테스트케이스들에서 적은 실행시간으로 통과할 수 있었다