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

문제

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

소요시간

40~50분, 옛날에 한번 봤던 문제라 조금 수월
너무 이쁘게(?) 구현하려고 조금 삽질
해결이 먼저다

코드

import heapq

def solution(jobs):

    q = []

    for j in jobs:
        heapq.heappush(q, (j[0], j[1])) #  요청시간, 작업시간

    now = 0
    n = 0 # completed
    elpsTime = 0 # total time used for disk op

    while n < len(jobs):

        if q[0][0] > now :
            now += 1
            continue # next iteration

        tmp_heap = []

        for i in range(len(q)):
            tmp = heapq.heappop(q)
            if tmp[0] <= now:
                heapq.heappush(tmp_heap, (tmp[1], tmp[0]))
            else:
                heapq.heappush(q, tmp)
                break

        obj = heapq.heappop(tmp_heap)
        elpsTime += (now - obj[1]) + obj[0] # 요청시간~현재시간 까지의 대기시간 + 작업시간
        now += obj[0]

        n += 1

        for item in tmp_heap:
            heapq.heappush(q, (item[1], item[0]))

    answer = elpsTime // n # 몫만 계산

    return answer

발상

1) job길이 1...500
요청시간이 0...1000
→ 순열이면 500! 개만큼 찾아야 하므로 안됨
→ 그리디한 방식으로 그때그때 최적이라 생각되는 해를 적용
하는 방식으로 해결해야 함
→ 요청이 짧은 순으로 해결하되, 현재 시점에서 해결할 수 있는 부분부터 짧은순으로 재정렬해서 해결