프로그래머스 level3 [디스크 컨트롤] 파이썬

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

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

def solution(jobs):
    answer = 0
    schedule = []
    jobs.sort()
    length = len(jobs)
    end = 0
    while jobs:
        if schedule: #대기 열이 존재하는 경우
            start, spend = schedule.pop()
            answer += (spend+end-start)
            end += spend
        else: #대기 열이 없는 경우
            start, spend = jobs.pop(0)
            answer += spend
            end = start+spend
        while jobs and jobs[0][0] <= end: # 작업이 끝나는 시간 전에 도착하는 작업들을 대기 열에 추가
            schedule.append(jobs.pop(0))
        schedule.sort(key=lambda x: -x[1]) # 작업의 시간을 오름차순으로 정렬
    schedule.sort(key=lambda x: -x[1])
    while schedule:
        start, spend = schedule.pop()
        answer += (spend+end-start)
        end += spend
    answer = answer//length
    return answer

디스크 작업에서 두가지 경우가 존재한다. (아무작업이 없는 경우는 제외)

1. 바로 작업을 받아서 시작하는 경우

2. 작업을 기다렸다가 끝나면 바로 이어서 시작하는 경우

 

작업이 끝나는 시간(end)가 다른 작업의 도착시간보다 크다면 작업의 정보가 schedule list에 저장된다.

한 번 while문을 돌때마다 정렬을 하기에 복잡도 측면에서는 좋지 않은 코드이다..

import heapq 
def solution(jobs): 
	answer, now, i = 0, 0, 0 
    start = -1 
    heap = [] 
    while i < len(jobs): # 현재 시점에서 처리할 수 있는 작업을 heap에 저장 
    	for j in jobs: 
        	if start < j[0] <= now: 
            	heapq.heappush(heap, [j[1], j[0]]) 
        if len(heap) > 0: # 처리할 작업이 있는 경우 
       		 cur = heapq.heappop(heap) 
             start = now 
             now += cur[0] 
             answer += now - cur[1] # 작업 요청시간부터 종료시간까지의 시간 계산
             i +=1 
        else: # 처리할 작업이 없는 경우 다음 시간을 넘어감 
        	now += 1 
        return answer // len(jobs)

출처: https://soohyun6879.tistory.com/136 [코딩기록]

다른 분의 힙을 이용한 풀이이다. 전체적인 코드는 비슷하지만, 힙을 이용했기 때문에, 시간 복잡도 측면에서 더 성능이 좋을 것으로 기대된다.