[Python] 디스크 컨트롤러 / 힙

 

 

 

 

---

문제

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

프로그래머스

 

 

코드

 

import heapq

def solution(jobs):
    jobs_len = len(jobs)
    jobs.sort(key=lambda x:x[0])
    heap = []
    total_time, current_time = 0, 0
    while jobs or heap:
        while jobs[0][0] <= current_time:
            job = jobs.pop(0)
            heapq.heappush(heap, (job[1], job[0]))
            print('heap:', heap)
            if heap:
                processing_time, starttime = heapq.heappop(heap)
                current_time += processing_time
                total_time += current_time - starttime
        else:
            current_time = jobs[0][0]
        
    print('totlal_time:', total_time)
    answer = total_time // jobs_len
    return answer

print(solution(jobs = [[0, 3], [1, 9], [2, 6]]))

 

 

 

다른 사람 코드

 

import heapq
from collections import deque

def solution(jobs):
    tasks = deque(sorted([(x[1], x[0]) for x in jobs], key=lambda x: (x[1], x[0])))
    q = []
    heapq.heappush(q, tasks.popleft())
    current_time, total_response_time = 0, 0
    while len(q) > 0:
        dur, arr = heapq.heappop(q)
        current_time = max(current_time + dur, arr + dur)
        total_response_time += current_time - arr
        while len(tasks) > 0 and tasks[0][1] <= current_time:
            heapq.heappush(q, tasks.popleft())
        if len(tasks) > 0 and len(q) == 0:
            heapq.heappush(q, tasks.popleft())
    return total_response_time // len(jobs)

 

 

 

접근법

 

1. jobs 리스트를 작업이 요청되는 시점 기준으로 오름차순으로 정렬합니다.
2. 현재 시간을 나타내는 변수를 초기화하고, 작업들을 차례로 처리합니다.
   1. 최소 힙을 사용하여 대기 중인 작업 중 소요시간이 가장 적은 작업을 선택합니다.
   2. 선택된 작업의 시작 시간이 현재 시간보다 이전이라면, 현재 시간을 시작 시간으로 업데이트합니다.
   3. 선택된 작업을 수행하고, 걸린 시간을 누적합니다.
3. 작업을 처리하는 동안 현재 시간을 업데이트하고, 모든 작업을 처리한 후에는 누적된 시간을 작업의 개수로 나누어 평균을 구합니다.

 

 

 

배운 점

힙을 더 능숙하게 사용 할 수 있게 되었다.