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

문제

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

"이거 완전 SJF이자나~~ 정처기 하면서 외웠다 rgrg" 외치면서 풀었는데
생각보다 오래 걸렸다 ㅎ

문제 풀이

작업 소요 시간이 짧은 순 ‣ 소요 시간이 같다면 요청 시점이 빠른 순
으로 정렬을 해주었다.

0. 입력 받고 정렬하기

import heapq
from collections import deque

def solution(jobs):
    answer = 0
    h = []
    curr = sys.maxsize
    temp = []
    for j in jobs:	# j :(작업 요청 시점, 소요 시간)
        heapq.heappush(h, (j[1], j[0]))
        if j[0] < curr:
            curr = j[0]

curr 에는 가장 짧은 소요 시간을 저장해주었다.

1. 힙의 첫번째 요소와 curr 과 비교해주기

while h:
    while h and curr < h[0][1]:
        time, arrived = heapq.heappop(h)
        heapq.heappush(temp,(time,arrived))

curr 보다 소요 시간이 길다면, 꺼내서 temp에 삽입해주었다.
힙의 최상단 요소의 소요 시간이 curr 과 같을 때까지 반복한다.

2. 힙이 비었는지 체크하기

사실 curr의 값을 가장 짧은 소요 시간을 해줘서
힙이 비어있을 일은 없을거라고 생각했다.

어림없지,, 런타임 에러가 발생했다.
열심히 질문 게시판을 찾아보니 이유를 알 수 있었다.

🔗 테스트 19번... 런타임 에러..
⭐️ 작업이 끝난 뒤 실행 될 다음 작업이 현재 시점보다 뒤에 있을 수 있다!

while문의 curr < h[0][1] 의 조건을 충족하지 못하기 때문에
힙의 모든 요소가 pop 된다.

따라서 힙이 비어있으면, curr을 1씩 증가시켜서
위의 조건을 만족시킬 때까지 반복해주자

   if not h:
        curr += 1
    else:
        # 힙에 요소가 있으면 pop 해준다.
        time, arrived = heapq.heappop(h)
        # 현재 시점인 curr에 소요 시간을 더해준다.
        curr += time
        # answer에 대기 시간을 더해준다.
        answer += (curr - arrived)

3. temp 요소들 다시 힙에 넣어주기

    while temp:
        t = heapq.heappop(temp)
        heapq.heappush(h, t)

소요 시간이 짧은 요소를 찾기 위해 임시로 빼둔 temp를
다시 h에 넣어준다.

4. h와 temp에 요소가 없을 때까지 반복

5. 평균 대기 시간 출력하기

    return (answer//len(jobs))

코드

import sys
import heapq
from collections import deque

def solution(jobs):
    answer = 0
    h = []
    curr = sys.maxsize
    temp = []
    for j in jobs:
        heapq.heappush(h, (j[1], j[0]))
        if j[0] < curr:
            curr = j[0]

    while h:
        while h and curr < h[0][1]:
            time, arrived = heapq.heappop(h)
            heapq.heappush(temp,(time,arrived))
        if not h:
            curr += 1
        else:
            time, arrived = heapq.heappop(h)
            curr += time
            answer += (curr - arrived)
            
        while temp:
            t = heapq.heappop(temp)
            heapq.heappush(h, t)
            
    return (answer//len(jobs))