[프로그래머스-Lv3] 디스크 컨트롤러 / Python

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

import sys
import heapq

input = sys.stdin.readline

jobs = [list(map(int, input().split())) for _ in range(int(input()))]


def solution(jobs):
    answer, now, i = 0, 0, 0
    start = -1
    q = []

    while i < len(jobs):
        for job in jobs:
            if start < job[0] <= now:
                heapq.heappush(q, (job[1], job[0]))
        if q:
            current = heapq.heappop(q)
            start = now
            now += current[0]
            answer += now - current[1]
            i += 1
        else:
            now += 1

    return answer // len(jobs)


print(solution(jobs))

 

해설

시작 시점에서 실행할 수 있는 작업들 중 작업길이가 작은 작업부터 실행하면 된다.

 

start = 시작지점, now = 작업이 끝난 시점

1. 이전 작업의 시작시점과 작업이 끝난 시점 사이에 도착한 작업들이 있으면 heaq에 저장한다.

2. 도착한 작업들이 존재한다면 작업시간이 제일 작은 작업을 꺼낸다.

3. 이제 시작지점은 이전 작업이 끝난 시점이 된다.

4. 작업 끝 시점은 이전 작업 끝 시점에서 현재 작업의 작업시간을 더한 시점이 된다.

5. answer에는 현재작업이 끝난 시점에서 현재 작업이 도착한 시점을 빼준 값을 더한다.

6. 2번 과정에서 도착한 작업들이 없다면 now를 1씩 증가시켜준다.