[알고리즘] 프로그래머스 - 디스크 컨트롤러

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

내 풀이

import heapq
import functools
import itertools
import re
import math
import bisect


def solution(jobs):
  cur_time = 0
  heap = []
  jobs.sort()
  ans = []
  while heap or jobs:
      jobs_remove_list = []
      # 현재 시각에서 작업 가능한 것들은 jobs에서 빼고 heap으로 옮긴다. 
      for i in range(len(jobs)):
          if jobs[i][0] <= cur_time:
              heapq.heappush(heap, (jobs[i][1], jobs[i][0]))
              jobs_remove_list.append(jobs[i])
      
      # 작업 가능한 것들을 따로 저장해놨다가 jobs에서 제거하는 과정이다.
      for remove_target in jobs_remove_list:
          jobs.remove(remove_target)
      
      # 힙에 작업할 것이 있다면, 걸리는 시간이 최소인것부터 작업하면된다.
      if len(heap) > 0:
          taken_time, ask_time = heapq.heappop(heap)
          cur_time += taken_time
          ans.append([cur_time, ask_time])
      
      # 작업할 수 없다면 시간이 1초 흐른다.
      else:
          cur_time += 1

  ans_sum = 0
  for i in range(len(ans)):
      ans_sum += ans[i][0] - ans[i][1]
  return ans_sum // len(ans)

힙을 이용해서 현재 작업 가능한 것 중, 작업 시간이 가장 짧은 것들부터 작업을 해나가면된다. 처음 heap.append()를 써서 오답이 나왔다. 리스트지만 힙으로 쓰고 싶으면 heapq.heappush(heap, item)을 써야한다.