Programmers_Python_heap_디스크 컨트롤러

문제링크

프로그래머스

프로그래머스_힙_디스크 컨트롤러

• 각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때,
• 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return.
• 입출력 예시

jobs	return (=평균)
[[0, 3], [1, 9], [2, 6]]	9

풀이방식

여기서 힙(heap) 이란?

• 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해
  고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)
• 힙으로 최대 최소 값을 찾아 우선순위 큐생성이 가능

핵심

• First Come First Served(FCFS)이 아닌  -->  " Shortest Job First(SJF)"
  즉 요청이 오는 순서대로가 아닌, 작업 소요시간이 짧은 순서대로 처리하는 것
• heapq 사용(힙 우선순위 큐)
  • 작업 소요시간이 짧은 순서대로 큐를 생성
  • heappush 와 heappop function 이용

코드 구현

• 누적 시간(ans), 현 시점(now), 처리량(i), 시작 시점(start)의 변수 생성
  • 현 시점(now) = 각 작업이 끝난 시점
• 총 처리한 량(i)이 총 작업 수(len(jobs))보다 커지기 전까지
  • 시작 시점과 현 시점 사이에 작업 요청시점이 존재하면 (즉 작업을 진행해야 할 시점이 도달)
    
    • 소요시간 짧은 순서대로
      • 우선순위 큐에 job 추가
      • 현 시점에 각 소요시간을 누적
      • 누적시간에 (현시점 - 각 작업 요청시점)을 누적
  • 시작 시점과 현 시점 사이에 작업 요청시점이 존재하지 않으면 (즉 작업의 요청 시점이 아직 도달하지 않음)
    • 현 시점을 +1 해나감
• 총 처리한 량(i)이 총 작업 수(len(jobs))에 도달하면 평균 구함

# job = [[0, 3], [1, 9], [2, 6]]
import heapq
def solution(jobs):
    ans,now,i = 0,0,0
    start = -1 
    h = []
    while i < len(jobs):
        for e in jobs:
            # 소요시간이 짧은 대로 리스트 추가 ( " Shortest Job First(SJF)" )
            if start < e[0] <= now: 
                heapq.heappush(h, [e[1],e[0]]) 
        if len(h)>0:
            curr = heapq.heappop(h)
            start = now # 시작 지점을 갱신 
            now += curr[0] # 소요시간을 누적
            ans += (now-curr[1]) # 총 걸린 시간 => (누적 소요시간 - 각 요청시점)을 누적
            i+=1
        # 맨 처음은 -1< < 0이니, 해당되는 요소가 없어 h가 비게 됨
        # now를 늘려나감
        else:
            now+=1
    # 평균
    return int(ans/len(jobs))