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

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

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

처음엔 이렇게 코드를 짰었습니다.. 애초에 소요시간으로 정렬한 후 현재 시점을 알 수 있는 now를 사용하여 작업 요청부터 종료까지 걸리는 시간을 계산하였습니다. 그런데....마지막 테스트케이스 빼고 다 실패^^가 떴습니다... 생각해보니 jobs = [[0,3], [2,1]]인 경우 이것을 정렬하면 [[2,1],[0,3]] 이 되는데 이 순서대로 실행이 불가능하다는 사실을 깨달았습니다... 처음부터 정렬하여 풀면 안된다는 것을 깨달았지만 이 코드를 버리고 어떻게 코드를 짜야할지 모르겠어서 다른 사람 풀이를 보고 이해를 했습니다...

def solution(jobs):
    answer, now = 0, 0
    jobs = sorted(jobs, key=lambda x: x[1]) 
    length = len(jobs)
    
    while jobs:
        for j in jobs:
            if j[0] <= now :
                now += j[1]
                answer += now - j[0]
                jobs.pop()
                break
            else:
                now += 1
        
    return answer // length

 

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)

찾아보니 이 코드가 가장 많이 보이는 코드였습니다! 저는 힙을 사용하지 않았었는데 힙을 사용하여 푸는 것이 더 좋아보입니다.

바로 이전에 작업을 완료한 시간(start)보다 크고 현재 시점(now)보다 작으면 현재 시점에서 처리할 수 있는 작업이 됩니다. 현재 시점에서 처리할 수 있는 작업을 heap에 저장합니다. 이 때 소요시간 기준으로 최소힙을 사용하기 때문에 heap에 저장할 때 [작업 소요 시간, 작업 요청 시간] 으로 저장합니다. heap의 길이가 0보다 크다면 처리할 작업이 있는 경우이므로 작업 요청시간부터 종료시간까지 계산하고 다음 작업으로 넘어갈 수 있도록 start 와 now 값을 바꾸어줍니다. heap의 길이가 0이라면 처리할 작업이 없는 경우이므로 현재 시점을 다음 시간으로 넘어가기 위해 now에 1을 더해줍니다. 마지막에는 평균 시간은 리턴해주면 됩니다.