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

[문제]

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

 

 

 

---

 

 

[풀이]

문제 해결을 위해 가장 짧은 실행 시간을 얻어내도록 job 실행 순서를 스케쥴링 해야한다. 스케쥴링에는 다음 두 가지를 고려한다.

1. 요구사항 가운데 먼저 요청된 job이 먼저 실행된다가 있으므로 job 수행 순서를 결정하는 첫 번째  기준은 "요청시각"이다.
2. 두 번째 기준은 실행시간인데, 이 "실행시간"이 heap을 통해 스케쥴링할 대상이다. 실행시간을 기준으로 스케쥴링을 하는 이유는 하나의 job도 실행되고 있지 않는 상태에서는 가장 빨리 도래하는 요청 건을 처리하면 되지만 어떤 job이 실행되고 있는 상태에서 여러 건의 요청이 들어온다고 한다면 그중 가장 짧은 실행 시간의 job부터 실행해야 나머지 요청 job들의 대기 시간이 줄어들어 결과적으로 총 실행 시간을 줄일 수 있기 때문이다.

 

즉, 간단히 말하면 요청 순서대로 정렬하여 처리하되 pendding 된 job들이 있는 경우 heap을 사용하여 그 job들을 수행시간을 오름차순으로 정렬하여 가장 수행시간이 짧은 job부터 연속적으로 수행되도록 하는 것이 이 문제의 골자이다.

 

 

문제를 해결하기 위해서 각 job의 수행 시간을 구해서 누적해야 하는데, 다음 두 가지 경우를 고려하여 job의 실행 시간을 알 수 있다.

현재 처리 중인 job이 있는 상태에서 요청이 들어오면 요청된 job은 현재 처리 중인 job이 완료된 직후에 실행된다.

위와 같은 경우 요청된 job의 실행 시간은 다음과 같다.

 

요청 job의 실행 시간 = 현재 job의 완료 시각 + 요청 job의 수행 시간 - 요청 job의 요청 시각

 

 

 

수행되는 job이 하나도 없는 상태에서 새로운 요청이 있다면 요청된 job의 실행 시간은 다음과 같다.

 

요청 job의 실행 시간 = 요청 job의 요청 시각 + 요청 job의 수행시간

 

 

위 내용을 바탕으로 본 문제를 해결하기 위한 의사 코드를 작성하면 다음과 같다.

# 첫번 째 정렬 기준 요청시각, 두번 째 정렬 기준 수행시간 으로 정렬
# 데이터를 수행시간, 요청시각으로 변경한 이유는 heap에서 수행시간을 기준으로 정렬해야 하기 때문임.
queue = sort([(수행시간, 요청시각), ...])

# 가장 먼저 시작되는 가장 짧은 수행시간의 job을 heap에 넣는다.
heap.push(queue.pop())

현재_job_종료시각 = 0
총_실행_시간 = 0

# heap에 내용이 있다는 것은 처리할 job이 있다는 뜻이므로
while heap is not empty:
    job_info = heap.pop()	# 실행 시간을 확인해야 할 job
    job_수행시간 = job_info[0]
    job_요청시각 = job_info[1]
    현재_job_종료시각 = max(현재_job_종료시각 + job_수행시간, job_요청시각 + job_수행시간)
    총 실행 시간 = 총 실행 시간 + 현재_job_종료시각 - job_요청시각

    # 실행 중인 job이 있어 pendding된 job들이 있는 경우
    while queue가 비어있지 않고 다음 요청 job의 요청 시각이 현재_job_종료 시각보다 앞에 오는 모든 경우:
    	heap.push(다음 요청 job 들)
    # 실행 중인 job이 하나도 없는 경우
    if queue가 비어있지 않고 heap에 내용이 없는 경우:
        heap.push(다음 요청 job)

answer = 총_실행_시간을 jobs의 길이로 나눈 몫

 

 

의사 코드를 바탕으로 python으로 구현해보면 다음과 같다.

import heapq
from collections import deque

def solution(jobs):
    jobs_q = deque(sorted([(job[1], job[0]) for job in jobs], key=lambda x:(x[1], x[0])))
    
    heap = list()
    heapq.heappush(heap, jobs_q.popleft())
    e_time = 0
    t_time = 0
    
    while heap:
        job_inf = heapq.heappop(heap)
        p_time = job_inf[0]
        r_time = job_inf[1]
		
        e_time = max(e_time + p_time, r_time + p_time)
        t_time += e_time - r_time
        
        while jobs_q and jobs_q[0][1] < e_time:
            heapq.heappush(heap, jobs_q.popleft())
        
        if jobs_q and not heap:
            heapq.heappush(heap, jobs_q.popleft())
            
    return t_time // len(jobs)