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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42627#

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

---

My Soulution

import heapq as hq


def solution(jobs):
    total = cur = i = 0
    cnt = len(jobs)
    jobs.sort()
    heap = []

    while i < cnt:
        while jobs and cur >= jobs[0][0]:
            item = jobs.pop(0)
            hq.heappush(heap, (item[1], item[0]))

        if heap:
            (time, start) = hq.heappop(heap)
            cur += time
            total += cur - start
            i += 1
        else:
            cur = jobs[0][0]

    return total // cnt

 

Key Idea

• jobs 를 sort하기 → 요청 시간 순서대로 저장되어있지 않을 수 있음
• 현재 시간(cur)를 기준으로 요청시간이 작은 것을 heap 에 넣기
• heap에서 한 개씩 꺼내서 작업하기
  → 처음에는 while 문으로 모두 돌려서 작업해서 오래걸림
  반례 : [[0, 3], [4, 4], [5, 3], [4, 1]] → 3
• 만약 현재 시간(cur)가 jobs의 첫번째 요청시간보다 작다면 cur 를 update
  → 이것도 작은 것을 예외로 두어 task 처리하는 방식으로 하다가 오래걸림.

 

Best Soultion과 알고리즘 상 큰 차이가 없고 가독성이 엄청 좋다고 생각되지 않아서 생략합니다.