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

https://school.programmers.co.kr/learn/courses/30/lessons/42627?language=ruby 

 

 

작성 코드 (실패)

 

from collections import deque



def solution(jobs):
    
    visit = deque(jobs)

    
    def dfs(total_time, visited, depth, wait_time, min_wait_time):
        print(1, total_time, visited, depth, min_wait_time)
        if depth == len(jobs):
            min_wait_time = min(min_wait_time, total_time)
            return min_wait_time
        for idx1, v in enumerate(visited):
            if not v:
                next_visit = visited[:]
                next_visit[idx1] = 1
                wait_time += max(0, total_time - jobs[idx1][0])
                total_time += 
                min_wait_time = jobs[idx1][0] - next_time
                next_time = max(total_time, jobs[idx1][0]) + jobs[idx1][1]
                
                dfs(next_time, next_visit, depth + 1, wait_time, min_wait_time)


    
    for idx2, [start_time, take_time] in enumerate(jobs):
        visit = [0] * len(jobs)
        visit[idx2] = 1
        print(22, dfs(start_time, visit, 1, jobs[idx2][0], float('inf')))

    return 0

 

• bfs로 풀어보려고 했으나 문제 조건이 까다로워 실패
• 힙 문제인데 힙으로 어떻게 푸는지 모르겠음

 

 

이상 코드

 

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