[프로그래머스]level3-디스크 컨트롤러-Python[파이썬]

문제링크

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

문제설명

알고리즘

main idea : 현재 시점에서 처리할 수 있는 작업들 중 소요시간이 가장 작은 작업들 먼저 처리
하지만 나는 이렇게 풀면 안된다고 생각했다.
ex) [0, 100] / [1, 3]이 주어질 때

• 왼->오 순서 : 100 + (100-1+3) = 100+102
• 오->왼 순서 : 3 + 104(1+3-0+100) = 107

위 예시에 따르면 오->왼 순서로 처리하는 것이 맞다.
하지만 main idea에 따르면 왼->오 순서로 작업을 처리하게 되므로 이 idea가 잘못된 줄 알았다.
하지만 내가 놓쳤던 부분이 있었다.

하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

이 조건을 적용하면 왼->오 순서로 처리하는 것이 맞고.. 그러므로 main idea는 맞는 것임.. (다음부턴 문제 제대로 읽어야지ㅜㅜ)

• 현재 시점에서 처리할 수 있는 작업 판별법
  : 요청 시간이 바로 이전에 완료한 작업의 시작 시간(start)보다 크고 현재 시점(now)보다 작거나 같을 경우 해당 작업은 현재 시점에서 처리 가능하므로 힙에 넣어준다.

만약 현재 처리할 수 있는 작업이 없다면, 남아 있는 작업들의 요청 시간이 아직 오지 않은 것이기 때문에 현재 시점(now)을 하나 올려준다.

코드

import heapq
def solution(jobs):
    jobs.sort() # 요청시점 순으로 정렬
    now = 0 # 현재 시점  
    hq = []
    answer = 0
    start = -1
    i = 0
    while i < len(jobs):
        for req_t, soyo_t in jobs[i:]:
            if start < req_t <= now:
                heapq.heappush(hq, [soyo_t, req_t]) # [소요시간, 요청시점]순서로 heap에 집어넣기
                # start = -1, now =3일때 // hq : [9, 3]
                # start = 3, now = 12일때 // hq : [8, 7] [6, 9]
                # start = 12, now = 18일때 // 추가할 것 없음. 남아있는 hq : [8, 7]
        if len(hq) > 0:
            curr = heapq.heappop(hq) # curr =[9, 3] // curr = [6, 9] // curr = [8, 7]
            start = now # start = 3 // start = 12 // start = 18
            now += curr[0] # now = 3 + 9 = 12 // now = 12+6=18 // now = 18+8=26
            answer += (now - curr[1]) # answer = 0 -> answer = 9 // answer = 9+9=18 // answer = 18+(26-7)=37
            i += 1
        else:
            now += 1
    
    return int(answer / len(jobs))