[Programmers] 디스크 컨트롤러

[Programmers] 디스크 컨트롤러

 

🎈문제

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

💬설명

• 우선순위 큐로 푸는 문제
• 기본 아이디어를 생각해내는건 어렵지 않았지만 문제 푸는 로직을 생각해내는게 조금 까다로웠다.
• 기본 아이디어: 특정 시점에 소요시간이 가장 작은 작업을 골라서 수행
• 풀이

while 모든 작업이 완료될 때까지:
	1. 현재 가능한 모든 작업 heapq에 넣기
    		가능한 작업의 기준: 들어온 작업들 마지막으로 체크한 시간(pre_time) < 요청 시간 <= 현재 시간(cur_time)
    	2. queue가 비어있는지 확인
    		2-1. 비어있지 않다면
        		heapq에서 가장 소요시간이 작은 값 pop
            		pre_time = cur_time  # 작업 마지막으로 체크한 시간 update
            		cur_time += pop한 작업의 소요시간
            		answer + (cur_time - pop한 작업의 요청시간)
            		완료된 작업 += 1
        	2-2. 비어있다면
        		cur_time += 1
            
 jobs의 개수로 나눠서 출력

👩‍💻코드

import heapq


def solution(jobs):
    jobs_len = len(jobs)
    answer = 0
    cur_time = 0
    pre_time = -1
    completed = 0
    hq = []
    
    while completed != jobs_len:
        # 이전에 확인했던 시점 - 현재 시점 사이에 추가로 들어온 작업들 hq에 넣기
        for job in jobs:
            if pre_time < job[0] <= cur_time:
                heapq.heappush(hq, [job[1], job[0]])
                
        # queue가 비어있지 않다면
        if hq:
            value = heapq.heappop(hq)
            pre_time = cur_time
            cur_time += value[0]
            answer += cur_time - value[1]  # 현재 실행되는 작업의 대기 + 소요 시간 추가
            completed += 1
        else:
            cur_time += 1
    
    return answer // jobs_len