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

🙄 참고하여 푼 풀이

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: #작업 시간이 now보다 작거나 같다면 
                heapq.heappush(heap, [j[1], j[0]]) #heap에 넣는데, 
                #[작업 소요시간, 작업 요쳥 시점]으로 요소의 앞 뒤를 바꿔 넣어준다.

        # 처리할 작업이 있는 경우
        if len(heap) > 0:
            cur = heapq.heappop(heap) #힙에 저장된 job을 꺼내 cur에 넣고
            start = now 
            now += cur[0] #작업 소요시간을 지금 시간으로 바꿔준다.
            answer += now - cur[1] 
            #작업 총 소요시간을 구하기 위해 answer에 더해 줌
            i += 1
        else :
            now += 1
    return answer // len(jobs)
print(solution([[0, 3], [1, 9], [2, 6]]))

🌌 문제풀이 흐름

처리시간이 짧은 순으로 일을 처리하면 빨리끝나나 -> 근데 이걸 어떻게 표현하지
-> 그래서 작업의 소요 시간 기준으로 최소 힙이 만들어 져야 한다!
-> heap 알고리즘을 써야 하는 이유
그래서 jobs의 요소를 그대로 넣는것이 아닌 [작업 소요시간, 작업 요쳥 시점]으로 요소의 앞 뒤를 바꿔 넣어준다.
그리고 시간이 지남에 따라 작업 총 소요시간을 answer 같은데에 담아 두고 job의 길이로 나누면 될듯

💛 참고한 곳들

안경잡이 개발자 heap 정렬
파이썬의 heapq 모듈로 힙 자료구조 사용하기
문제풀이 참고한 블로그