[Programmers] 디스크 컨트롤러

디스크 컨트롤러

디스크 컨트롤러 를 클릭하면 바로 이동한다.

가능한 작업 중 작업 시간이 가장 작은 작업 순으로 수행하면 된다.

[0, 3], [1, 9], [2, 6] 의 작업이 주어질 때, 먼저 3초가 소요되는 작업을 수행한다.

이 작업을 수행하는 도중 [1, 9], [2, 6] 의 작업이 주어지는데 이 때 작업 시간이 작은 [2, 6], [1, 9] 순으로 진행한다.

작업 시간이 작은 순으로 수행해야 하기 때문에 힙에는 작업 시간을 큰 순서대로 넣어야지 나중에 빼서 사용 할 때 작은 순으로 작업을 할 수 있다.

풀이를 생각해도 그걸 코드로 바꾸는 능력이 부족한 것 같다.

프로그래머스 문제 풀이 디스크 컨트롤러 이 분의 풀이를 참조 해 풀었는데 나도 이제 코드마다 설명을 적어야 할 것 같다..

---

import heapq
from collections import deque


def solution(jobs):
    # 1. 가장 먼저 할 작업 선정
    jobs.sort(key=lambda x: (x[0], x[1]))
    # 2. 먼저 수행 할 작업을 왼쪽에 넣고 뺄 것이기 때문에 deque 선언
    jobs = deque(jobs)
    # 3. 평균 작업 시간을 계산하기 위한 전체 작업 시간과 작업 개수
    total_time = 0
    n = len(jobs)
    # 4. 맨 처음 작업 종료 시간
    time = jobs[0][0]
    # 5. 작업 시간이 가장 큰 작업 정렬 용 힙 선언
    heap = []

    while jobs:
        # 6. 수행 할 작업 선정
        request, work = jobs.popleft()
        # 7. 작업 종료 후 시간
        time += work
        # 8. 작업 종료 후 시간에서 기다린 시간을 빼 전체 소요시간을 구한다
        total_time += time - request

        # 9. 작업이 끝나기 전에 요청 된 새로운 작업들 가져오기
        while jobs and jobs[0][0] < time:
            request, work = jobs.popleft()
            # 10. 최대힙으로 해야 나중에 작업 시간이 작은 순으로 넣어 줄 수 있다
            heapq.heappush(heap, (-work, request))

        # 11. 가져온 작업들 중 작업 시간이 가장 큰 순서로 넣어주기
        while heap:
            work, request = heapq.heappop(heap)
            jobs.appendleft((request, -work))

    return total_time // n


if __name__ == "__main__":
    jobs = [[0, 10], [4, 10], [15, 2], [5, 11]]
    print(solution(jobs))