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

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

풀이

그리디+힙으로 생각을 하였다. 처음에는 단순히 시간이 적게 거리는 작업을 먼저 해야된다는 생각을 하였는데, 단순히 시간이 적게 걸린다고 요청 시간을 생각하지 않고 먼저 처리할 수는 없었다. 그래서 생각해낸 조건이 현재의 시각을 계산하여 현재 시각 내에서 요청이 들어온 작업 중에서 시간이 가장 적게 걸리는 작업을 선택하게 하였다. 만약 리스트나 다른 자료구조를 사용한다면 탐색하고 pop해주는데에 시간이 너무 오래 걸릴 것이다. 그래서 heap을 사용하여 우선순위큐를 구현해주었다. heap에다가 일단 작업하는 데에 필요한 시간을 기준으로 최소 힙을 만들어주고, 현재 시간을 선언해주고 하나씩 pop해준 다음 만약 요청 시간이 현재 시간보다 적을 시(이미 요청이 됬다)  loop를 멈추고 현재 시간에 작업 시간을 더해준 후, answer에 현재 시간 - 요청 시간을 더해주면 된다. 마지막에 평균 시간을 구하라고 했기 때문에 jobs의 길이만큼 나눠주면 된다.

import heapq
def solution(jobs):
    answer = 0
    heap = []
    t = 0
    for j in jobs:
        heapq.heappush(heap, [j[1], j[0]])
    while heap:
        tempt = []
        flag = False
        min_time = 1e9
        while heap:  
            a = heapq.heappop(heap)
            if min_time > a[1]:
                min_time = a[1]
            if a[1] <= t:
                t += a[0]
                answer += t - a[1]
                flag = True
                break
            else:
                tempt.append(a)
        if tempt:
            for k in tempt:
                heapq.heappush(heap, k)
        if not flag:
            t = min_time
    answer //= len(jobs)
    return answer