Programmers. 디스크 컨트롤러

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 디스크 컨트롤러

문제 풀이

요청과 처리 완료에 들어가는 시간이 평균적으로 짧아야 한다. 다만 한 번에 한 개의 작업만 가능하다는 점에서 길이가 긴 작업을 먼저 진행하면 뒤이은 작업은 길이가 긴 작업의 진행 시간만큼 대기해야 하므로 평균 처리 시점의 증가로 이어진다.

하나의 작업을 진행하는 동안 접수된 작업 요청들 중 가장 길이가 작은 것들을 우선 처리하고 이후 시점을 갱신하여 다시 대기열을 추가하는 작업이 필요하다.

• 모든 주어진 작업을 완료해야 하므로 전체 진척도를 별도의 값으로 기록한다. 버퍼 count의 값이 주어진 작업 배열의 길이와 같아질 때까지 반복하면 된다.
• 각 순회 단계에서 어떤 작업을 처리할 지 대기열을 생성해야 한다. 우선 요청 시간 범위start, end를 [-1, 0]으로 두고 주어진 작업들 중 해당 요청시간 범위에 있는 작업들을 [작업 시간, 요청 시각]으로 바꿔 대기열 힙에 저장한다.
• 만약 대기열 힘에 삽입된 작업이 있으면 pop한 뒤 작업 count를 1 더한다. 이후 요청 접수 시작 시간을 기존 시각으로 바꾸고 작업이 진행되었다는 가정 하에 현재 시간을 작업 종료 시간으로 바꾼다.
• 만약 대기열 힙에 어떤 작업도 삽입되지 않았다면 요청 접수 시간이 짧음을 의미하므로 현재 시점에서 1을 더한다.

python 코드

import heapq

def solution(jobs):
    start, now = -1, 0
    heap = []
    cnt = 0
    answer = 0
    while cnt < len(jobs):
        for job in jobs:
            if start < job[0] <= now:
                heapq.heappush(heap, [job[1], job[0]])
        if heap:
            x = heapq.heappop(heap)
            cnt += 1
            start = now
            now += x[0]
            answer += now - x[1]
        else:
            now += 1
    return answer // len(jobs)