[힙] 디스크 컨트롤러 (파이썬)

문제 설명

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

프로그래머스

문제 풀이

• 현재 시점(time)에서 처리 할 수 있는 작업들을 힙에 모두 넣어줌
• 현재 시점에서 작업이 가능한 것들이 있다면(len(q)>0) 끄집어내서 처리해줌.
• 이 때 힙에 넣어준 것이므로 pop을 해준다면 가장 소요되는 작업량이 작은 값이 나올 것. (이 때 나오는 것은 작업량 기준으로 힙에 넣은 것이므로 node[0]은 소요시간, node[1]은 작업 시작 시간임) 
• 그럼 이후의 작업 할 디스크를 찾기 위해 start를 현재 시간(time)으로 잡아주고 
• time에는 작업 소요 시간 node[0]을 더해 줌 
• answer는 총 시간인 time을 더해주고, 시작 시간은 빼야 하므로 node[1]을 빼줌
  • 만약 현재 시점 time에 작업 할 것이 없다면 q는 길이가 0이므로 time에 +1을 해줘서 그 다음 시간들의 작업 체크

오답노트

# jobs를 정렬
# 작업시간, 실제 시간, 방문 체크 를 큐에 넣어준 뒤 
# 만약 다음으로 올 작업의 시작 시간이 현재 총 시간보다 크다면 현재 시간에 할 수 있는 것들이 빈 것이므로 
	# 이 작업을 큐에 넣어준 후 break 해줌
# 다음으로 올 작업의 시작 시간이 현재 총 시간보다 작다면 작업 시간을 계산해서 큐에 넣어줌

#이럴 경우 시간 초과 뜸


import heapq
from copy import deepcopy
INF =int(1e9)

def solution(jobs):
    jobs.sort()
    n = len(jobs)
    q = []
    heapq.heappush(q,(jobs[0][1],sum(jobs[0]),0,1,[0]))
    while(q):
        job, time, cur, leng,v = heapq.heappop(q)
        if(leng==n):
            return job//n
        for i in range(n):
            if i in v:
                continue
            if jobs[i][0]>time:
                heapq.heappush(q,(job+jobs[i][1],time+sum(jobs[i]),i,leng+1,v+[i]))
                break
            else:
                heapq.heappush(q,(job+time-jobs[i][0]+jobs[i][1],time+jobs[i][1],i,leng+1,v+[i]))

 

소스코드

# jobs의 길이는 1 이상 500 이하입니다.
# jobs의 각 행은 하나의 작업에 대한 [작업이 요청되는 시점, 작업의 소요시간] 입니다.
# 각 작업에 대해 작업이 요청되는 시간은 0 이상 1,000 이하입니다.
# 각 작업에 대해 작업의 소요시간은 1 이상 1,000 이하입니다.
# 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.
import heapq

def solution(jobs):
    jobs.sort()
    n = len(jobs)
    answer, time, cur = 0,0,0   #구하고자 하는 작업량, 작업을 통한 현재 시간, 현재 노드
    start = -1
    q = []
    while(cur<n):
        for next in jobs:
            if start<next[0]<=time:
                heapq.heappush(q,(next[1],next[0]))
        if(len(q)>0):
            node = heapq.heappop(q)
            start=time
            time+=node[0]
            answer+=time-node[1]
            cur+=1
        else:
            time+=1
    return answer//n
    

print(solution([[0, 3], [1, 9], [2, 6]]))