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

문제 설명

제한사항 및 입출력

풀이

문제 설명에서 볼 수 있듯이 각 작업에 우선순위가 주어지고 이 우선순위(소요시간, 요청 시각)를 기반으로 작업을 처리해야한다. 작업 큐에서 매번 가장 작은 우선순위를 순회하며 찾을 순 없으니 힙(heap)을 사용하여 가장 작은 우선순위를 빠르게 찾을 수 있도록 해주었다. 또한 소요시간과 요청 시각이 같다면 작업의 번호가 작은 것을 우선순위로 본다고 했는데, 사실 소요시간과 요청 시각이 같다면 무엇을 먼저 처리하든 구하려는 정답에는 차이가 없기 때문에 제외하고 2가지만 고려해주었다.

내 코드

from heapq import heappush, heappop
from collections import deque

def solution(jobs):
    # 요청 시각 기준으로 정렬
    jobs.sort()
    jobs = deque(jobs)

    time = 0        # 현재 시각
    heap = []       # 대기 큐
    total_time = 0  # 전제 작업의 소요 시간
    job_length = len(jobs)
    idx = 0
    while idx < job_length:
        # 현재 시각까지 도착한 작업들을 힙에 넣기
        while jobs and jobs[0][0] <= time:
            request, duration = jobs.popleft()
            heappush(heap, (duration, request))

        # 대기 큐가 있다면
        if heap:
            duration, request = heappop(heap)
            time += duration
            total_time += time - request
            # 실제로 작업이 처리될 때만 증가
            idx += 1
        else:
            # 대기 큐가 비어있으면 다음 작업의 요청 시각으로 이동
            if jobs:
                time = jobs[0][0]

    return total_time // job_length

주어진 작업 큐에서 현재 시간보다 작은 시간의 작업들을 모두 힙에 넣고 힙이 비어있지 않다면 하나씩 꺼내서 작업을 처리해주었다.

 

시간 복잡도: O(n logN)

-> 힙 연산이 log n이고 총 n번 반복