[programmers] Heap - 디스크컨트롤러

문제링크

---

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

문제 해설

---

IN

• jobs : [작업이 요청되는 시점, 작업의 소요시간]
  

OUT

• 작업의 최소 평균 요청~종료 소요시간

제한사항

• 소수점 이하의 수는 버림
• 1<= len(jobs) <= 500
• 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
• 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
• 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.

문제 접근

---

SJF

이 문제에서 최소인 평균 대기시간을 구하기 위해서는 소요시간이 짧은 작업을 먼저 처리해야 한다.

따라서 FIFO의 단점을 보완한 SJF 스케줄링 알고리즘을 이용해야함!

SJF란?

: Shortest Job First

→ CPU burst가 적은 것부터 수행하는 스케줄링 방식

코드

---

import heapq
def solution(jobs):
    in_time = -1
    out_time = 0
    n = len(jobs)
  	#작업 시간이 짧은 job부터
    jobs.sort(key = lambda k:k[0])
    heap = []           
    time = []
    sum = 0
    count = 0
                
    while count < n: 
        //모든 job이 처리될 때 까지
        for job in jobs:
            if in_time < job[0] <= out_time:     
            //마지막 요청시간~처리시간동안 요청한 job찾기
                heapq.heappush(heap, [job[1], job[0]])
        
        if len(heap) > 0:
  			//앞의 작업 진행중 요청한 job있으면
            job = heapq.heappop(heap)
            in_time = out_time
            out_time += job[0]
            count += 1
            time.append(out_time-job[1])
        
        else:
            out_time += 1

    for t in time:
        sum += t
    
    return int(sum/n)

• python의 heap을 이용해서 구현했다.

• 전체 job이 아닌 앞의 job을 처리하는 동안 작업을 요청한 job에 대해서만 heap에 저장을 하는것이 포인트임!!!

• SJF의 구현을 위해 heap에 들어가는 job을 [작업 소요시간, 요청시점] 순으로 push한다 .

  → heap은 리스트의 경우 첫번째 원소에 대해 정렬하기 문에

• while조건을 while jobs: 로 두고 job.remove()했더니 포문이 잘못 돌아서 한참 해멨다.