Level 3 디스크 컨트롤러 Python 3

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

코딩테스트 연습 - 디스크 컨트롤러

 

최종 코드

• GitHub https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_디스크컨트롤러.py

hwayeon351/Programmers-Algorithms

import heapq
def solution(jobs):
    answer, now, cnt = 0, 0, 0
    start = -1
    min_heap = []
    while cnt < len(jobs):
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(min_heap, [j[1], j[0]])
        if len(min_heap) > 0:
            job = heapq.heappop(min_heap)
            start = now
            now += job[0]
            answer += (now-job[1])
            cnt += 1
        else: now += 1
    return answer//len(jobs)

---

풀이 과정

시간을 카운팅하여 현재 시간에 수행할 수 있는 작업들을 min heap에 넣어 최소 소요 시간을 가진 작업을 수행하는 방식으로 풀었다.

현재 시간에 수행할 수 있는 작업은 이전 작업의 종료 시간 ~ 현재 시간 사이에 요청한 작업 + 전에 요청된 작업인데 수행하지 않아서 min_heap[]에 쌓여있는 작업이다.

이중에서 가장 작은 소요시간을 가진 작업을 먼저 수행하는 것이 작업을 모두 처리하는데 걸리는 시간을 줄일 수 있는 방법이다.

 

heapq.push()로 반복가능한 객체를 넣으면 첫번째 요소를 기준으로 부모 노드가 자식 노드보다 작은 완전 이진 트리 구조로 min heap이 구성된다.

import heapq
def solution(jobs):
    #현재 시간 now, 수행한 작업 수 cnt, 이전 작업이 끝난 시간 start
    answer, now, cnt = 0, 0, 0
    start = -1
    #부모 노드의 작업 소요 시간이 자식 노드보다 작은 min heap 표현
    min_heap = []
    
    #수행된 작업의 수가 총 작업 수와 같아지면 종료
    while cnt < len(jobs):
        #이전 작업의 종료시간 ~ 현재 시간에 들어온 작업 heap에 push
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(min_heap, [j[1], j[0]])
        #수행할 작업이 있는 경우
        if len(min_heap) > 0:
            #해당 작업을 힙에서 pop()하여 수행
            job = heapq.heappop(min_heap)
            #해당 작업의 시작 시간은 현재 시간으로 바꿔주고, 현재 시간에 해당 작업의 소요시간을 더해준다.
            start = now
            now += job[0]
            #해당 작업의 요청(job[1])부터 종료(now)까지 걸린 시간을 answer에 더해주고, cnt 카운팅
            answer += (now-job[1])
            cnt += 1
        #수행할 작업이 없는 경우 현재 시간을 카운팅한다.
        else: now += 1
    #모든 작업을 수행하는데 총 걸린 시간(answer)에 작업의 수를 나눠 평균 시간을 return
    return answer//len(jobs)
#시간복잡도 = O(n^2log n) 공간복잡도 = O(n)