[Programmers] 디스크 컨트롤러 (Python 풀이)

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

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

이 문제를 풀기 위해서는 python의 heapq 라이브러리를 다룰 수 있어야합니다.
관련 정보는 다음 사이트를 참고하세요. https://docs.python.org/ko/3/library/heapq.html

---

 

import heapq
def solution(jobs):
    job_count = len(jobs)
    t_now = 0 # 현재시간
    t_working = 0 # 총 소요시간
    heap = []
 
    while True:
        # 작업 중 현재 시작 가능한 작업(작업 시작 시간 <= 현재 시간)만 heap에 추가함
        for start_t, working_time in [j for j in jobs if j[0] <= t_now]:
            heapq.heappush(heap, (working_time, start_t))         # 작업 길이를 기준으로 heap에 추가
            
        jobs = [j for j in jobs if j[0] > t_now] # 남은 작업 갱신 (작업 시작 시간 > 현재 시간)
 
     
        if not heap and not jobs:    # 만약 남은 작업이 모두 없는 경우 break
            break
 
        if not heap:  # 남은 작업은 있으나 heap에 아무것도 없는 경우         
            t_now += 1 # -> 남은 작업 중 시작 가능한 작업이 없음, 현재 시간을 +1
            continue
 
        # 가장 우선순위의 작업을 가져와 작업 수행
        l, t = heapq.heappop(heap)
        t_now += l
        t_working += t_now - t # 소요시간 : 작업 완료 시간 - 작업 요청 시간
 
    return t_working // job_count # 평균 작업 시간 반환

 

10~11번 라인 : 요청 작업의 요청 시간을 기준으로 현재 시간보다 같거나 적은(t_now 시점에 시작 가능한 작업)을 모두 heap에 추가합니다. heap에 추가할 때 작업 시작 시간을 기준으로하는 것이 아니라 작업 소요 시간을 기준으로 heap에 추가합니다. (현재 처리 가능한 작업 중 가장 짧게 걸리는 작업 부터 수행)

13번 라인 : heap에 추가된 작업을 제외하여 다시 리스트를 구성합니다.

19~21번 라인 : job 리스트에는 작업 내용이 남아있지만, heap에 아무 것도 없는 경우입니다. 이 경우에는 t_now 시점에 실행 가능한 작업이 없으므로 t_now를 1증가 시키고 다시 반복문을 실행합니다.

24~26번 라인 : 작업을 수행합니다. 작업 수행시간은 작업 완료시간 - 작업 요청 시간이며 총 작업 시간에 이를 추가합니다.

28번 라인 : 작업 시간의 평균을 반환합니다. 소수점은 버리므로 몫만 반환합니다.

---

 

실행 결과