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

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

책을 보고 검색 해보고 남의 코드를 그대로 사용해보고 직접 코드를 작성해보고 꾸준히 많은 시간을 써서 코딩테스트를 준비해보기로 했습니다!

해결방법:

주어진 작업을 처리하는데 평균 걸리는 시간을 최소화하려면, 최소 힙 (Min Heap) 자료구조를 사용하여 작업을 관리해야 합니다. 다음과 같은 단계로 문제를 해결할 수 있습니다:

작업 리스트를 작업이 요청된 시간에 따라 정렬합니다.
현재 시간을 0으로 초기화하고, 결과를 저장할 변수를 선언합니다.
빈 힙(Heap)을 생성하고, 작업 리스트에서 첫 번째 작업을 힙에 추가합니다.
현재 시간을 힙에서 가장 작은 소요시간을 가진 작업의 요청 종료 시간으로 갱신합니다.
힙에서 작업을 제거하고 결과 변수에 현재 시간에서 작업이 요청된 시간을 뺀 값을 더합니다.
작업 리스트에 남은 작업 중에서 현재 시간보다 이른 요청 시간을 가진 작업을 모두 힙에 추가합니다.
위의 단계를 반복하며 모든 작업을 처리합니다.
위의 알고리즘을 구현하면 평균 걸리는 시간을 최소화할 수 있습니다. 이때, Python의 heapq 모듈을 사용하면 간단하게 최소 힙을 관리할 수 있습니다.

작성코드:

import heapq

def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1 
    heap = []
    
    while i < len(jobs):
        # 현재 시점에서 처리할 수 있는 작업을 heap에 저장
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
        
        if len(heap) > 0: # 처리할 작업이 있는 경우
            cur = heapq.heappop(heap)
            start = now
            now += cur[0]
            answer += now - cur[1] # 작업 요청시간부터 종료시간까지의 시간 계산
            i +=1
        else: # 처리할 작업이 없는 경우 다음 시간을 넘어감
            now += 1
                
    return answer // len(jobs)