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

문제

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

프로그래머스

 

풀이

1. 주어지는 작업은 정렬되어 있다는 가정이 존재하지 않는다. 그러므로 시작시간을 기준으로 정렬한다. (난 그냥 heapq를 사용해서 오름차순 정렬을 했음)

2. 정렬된 작업들에서 마지막에 수행된 작업시간 이전에 요청된 작업을 뽑는다.

3. 뽑은 작업들을 다시 heapq에 담는다 대신 작업의 소요시간 순으로 오름차순 정렬될 수 있도록 한다.

4. 그 중 가장 작업 소요시간이 가장 짧은 작업을 처리하고 요청 시간부터 현재 시간까지의 차를 리스트에 넣는다. 그 후 나머지 작업들은 다시 정렬된 작업들에 돌려 놓는다.

5. 작업을 처리 할 때, 현재 시간을 갱신한다. 만약 현재 시간내에 수행할 작업이 없다면 현재시간에 1을 더한다.

6. 2~5 과정을 반복한다.

7. 요청 시간부터 현재 시간까지의 차를 담은 리스트의 평균을 구한다.

 

import heapq

def solution(jobs):
    answer = 0
    
    req_time = []
    
    ans_list = []
    sum_time = 0
  
    for job in jobs:
        heapq.heappush(req_time,job) # 1번 설명
    
    while req_time: # 6번
        exe_time = []
          
        while req_time :
            req = heapq.heappop(req_time)
            if req[0] <= sum_time: # 2번
                heapq.heappush(exe_time,[req[1],req[0]]) # 3번
            else:
                heapq.heappush(req_time,req)
                break
            
        if exe_time:
            exe = heapq.heappop(exe_time)

            sum_time += exe[0]	# 4번
            ans_list.append(sum_time - exe[1])
            
            while exe_time:
                exe = heapq.heappop(exe_time)
                heapq.heappush(req_time,[exe[1],exe[0]])
        else:
            sum_time += 1 # 5번
                 
    answer = sum(ans_list) // len(ans_list) # 7번
    
    return answer