프로그래머스 디스크 컨트롤러(Python3)

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

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

이번에 코딩 테스트 연습하고자 처음 잡아본 문제가 이 디스크 컨트롤러 문제다.

열심히 생각해봤으나 결국 혼자의 힘으로 풀지 못했고 아래의 사이트에서 배웠다.

https://dev-note-97.tistory.com/150

[프로그래머스] 디스크 컨트롤러 / Python

코드 설명

1. input으로 들어오는 jobs에 대해 SJF scheduling(가장 짧게 걸리는 job을 scheduling)을 적용한 결과를 담을 heap 변수를 빈 리스트로 초기화(schedule_heap)
2. heap 안에 담기는 job이 끝나는 시간의 합을 저장하기 위한 변수를 0으로 초기화(time)
3. 요청 시간이 time보다 작거나 같은 job들을 heap에 push(push 할 때 [걸리는 시간, 요청 시간] 형식으로 바꿔서 push 해야 SJF 방식으로 heap 정렬 가능) push 후 heap이 비어있다면 time을 가장 빠른 요청 시간으로 변경 후 다시 push 실행
4. heap에서 pop한 item을 가지고 time, answer 계산
5. answer를 jobs의 길이로 나눠서 return(정수형)

전체 코드는 아래와 같다.

import heapq

def solution(jobs):
    schedule_heap = []
    time, answer = 0, 0
    jobs_cnt = len(jobs)
    jobs.sort()
    while len(schedule_heap) != 0 or len(jobs) != 0:
        while len(jobs) != 0 and jobs[0][0] <= time:
            heapq.heappush(schedule_heap, jobs.pop(0)[::-1])
        
        if len(schedule_heap) == 0:
            time = jobs[0][0]
            continue
            
        now_process = heapq.heappop(schedule_heap)
        time += now_process[0]
        answer += time - now_process[1]
    return answer // jobs_cnt

여기서 python built-in 모듈 'heapq'를 사용했다. heapq의 사용법은 아래의 document를 참고하자.

https://docs.python.org/ko/3.8/library/heapq.html?highlight=heapq#module-heapq

heapq — Heap queue algorithm — Python 3.8.13 문서