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))