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

 

 

 

 

 

 

 

 

 

 

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

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

 

 

 

 

이 문제 어디선가 푼적이 있는것 같다.

뭔가 그리디 하면서 비슷한것을 본것같은데 못풀었다...

백준 회의실..?

 

 

 

 

---

 

 

 

이 문제를 푸는 방법은 

 

그 기간에서 할 수 있는 작업 중 소요시간이 가장 짧은 것을 먼저 실행하면 된다.  

 

그러기위해 heappush할 때 [1][0]으로 넣어주는 것을 기억해야한다. 

왜냐하면 소요시간이 짧은 순으로 먼저 나와야하기 때문이다. 

 

 

 

코드의 설계 : 

 

1. heap에 들어갈 수 있는 시간을 정하고 (초기에는 -1부터 0까지)[실행이 가능한 작업들을 구분하기위해]

<while 문은 실행하는 작업의 수를 나타내는 i를 이용해 실행 조건을 만든다.>

2. 기간안에 있는 것들을 heappush

3-1. heap안에 뭔가 있다면 start, now를 조정하고 answer에도 값을 더해준다.

3-2. heap안에 뭔가 없다면 now +=1 을 통해 기간을 늘려준다.  

4. answer 를 작업의 수로 나누어 평균을 구해 return 한다.  

 

 

 

코드 : 

 

import heapq
def solution(jobs):
    answer ,now, i= 0,0,0 
    start = -1 
    heap = []
    while i < len(jobs) : # 수행할 작업이 수행한 작업보다 작을동안 
        for j in jobs :
            if start < j[0] <= now : # 해당 구간에서 시작하는 것들을 heap에 넣음 
                heapq.heappush(heap,[j[1],j[0]]) # 실행시간이 작은 것 부터 실행하기위해 j[1]을 먼저 
        if len(heap) > 0 : # heap에 뭐가들었다면  
                cur = heapq.heappop(heap)
                start = now 
                now  += cur[0]
                answer += (now - cur[1]) # (현재 시간에서 작업이 할당된 시간을 빼서) 구한 기다린 시간을 answer에 더해줌
                i+=1 # 한 작업 수행했음을 알림 
        else : # 안들었다면 시간을 늘려줌 
            now+=1 
    return answer//len(jobs)

 

 

 

heap 에 아무것도 들어있지않을 때 now +=1을 통해 힙에 들어갈 수 있는 작업의 범위를 넓힌다. 

 

 

i 라는 변수를 만들어 실행한 작업의 개수가 작업의 개수보다 작을 동안 실행한다.

그리고 start 는 now로 할당된다는 것을 잊지말자. 

 

 

 

 

복습 : 

✅ 20220618

✅ 20220620

✅ 20220622

✅ 20220626

✅ 20220627

✅  20220630