[Python] 프로그래머스(Lv3) - 디스크 컨트롤러

안녕하세요 !

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

힙 문제이지만 ... 이해하기 쉬운 코드를 발견해서 이렇게도 제출해보았습니다.

참고

풀이

먼저, 소요시간을 기준으로 오름차순 정렬해줍니다. 소요시간이 짧은 순서대로 처리를 해줘야 총 시간이 덜 소요되기 때문입니다.

그렇다고 소요시간이 짧은 순서대로 무조건 처리하는 것은 아닙니다!
요청시간이 start(현재까지 진행된 작업시간) 보다 작거나 같으면 처리를 해줍니다.
jobs를 다 돌았는데도 아직 작업이 들어오지 않았다면 start++를 해줘서 시간을 늘려줍니다.

def solution(jobs):
    answer = 0
    start = 0  # 현재까지 진행된 작업 시간
    length = len(jobs)

    jobs = sorted(jobs, key=lambda x: x[1])  # 소요시간 우선 정렬

    while jobs:
        for i in range(len(jobs)):
            if jobs[i][0] <= start:
                start += jobs[i][1]
                answer += start - jobs[i][0]
                jobs.pop(i)
                break
                
            # 해당시점에 아직 작업이 들어오지 않았으면 시간 ++
            if i == len(jobs) - 1:
                start += 1

    return answer // length

힙을 쓰면 아래와 같이 풀이를 할 수 있습니다.
위 풀이와 거의 비슷한 방법입니다. 요청시간이 start와 now 사이라면 heap에 넣어줍니다.
heap에 넣으면 자동으로 정렬되어 heappop을 하면 최소값을 구할 수 있습니다.
heap이 존재한다면 heappop을 한 current 값을 이용해 값을 구해주고,
존재하지 않는다면 now++로 시간을 늘려줍니다.

import heapq

def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1
    heap = []

    while i < len(jobs):
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
        if heap:
            current = heapq.heappop(heap)
            start = now
            now += current[0]
            answer += (now-current[1])
            i += 1
        else:
            now += 1
            
    return answer // len(jobs)