[Programmers] Level 3. 디스크 컨트롤러

🔗 Problem Link

프로그래머스

---

❔Thinking

• 대기열에 등록된 시간과 작업 시간이 주어질 때, 작업에 요청부터 종료까지 걸리는 평균 시간의 최소값을 반환한다.
• 작업에 요청부터 종료까지 걸리는 시간은 '대기시간' 및 '작업 시간'을 포함한 시간이다.

---

💻Solution

import heapq
def solution(jobs):
    n = len(jobs)
    total_task_time = 0
    current_time = 0
    q = []
    jobs = sorted(jobs, key=lambda x: (x[0], x[1]))
    while jobs or q:
        # 현재 수행 가능한 작업 q에 등록
        while jobs and jobs[0][0] <= current_time:
            j = jobs.pop(0)
            heapq.heappush(q, [j[1],j[0]])
        # q에 등록된 작업 수행
        if q:
            needed_time, register_time = heapq.heappop(q)
            total_task_time += (current_time - register_time) + needed_time
            current_time += needed_time
        else:
            current_time += 1
    return total_task_time // n

---

🗝️keypoint

1. heapq 구조는, 최소/최대 값을 반환하는 트리 구조이다.
2. 시간을 최소한으로 만들기 위해서는 대기 시간이 가장 짧아야 한다.
3. heapq에 list를 넣을 경우, 첫 인덱스를 기준으로 정렬하고 이후에는 원래의 순서를 따른다.