Heap - 디스크 컨트롤러

이번문제는 Heap을 사용하여, 최소의 시간으로 정렬된 리스트를 만드는 문제입니다.

(+욕심쟁이 방법론)

https://programmers.co.kr/learn/courses/30/lessons/42627

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

이번 문제는

 

[[Event1 발생시간, Event1 처리에 걸리는시간],,,,,]

 

의 형태로 다수의 Event가 존재할 때

 

"Event가 발생~Event가 처리가 완료" = 소요시간

 

이때, 모든 Event의 소요시간의 평균값을 가장 작게 만드는게 이번 문제입니다.

 

이를 위해서, 욕심쟁이 방법론을 활용합니다.

 

모든 Event는 고유하게 처리하는데 걸리는 시간이 존재합니다.
그렇다면, 매 시점마다 처리에 걸리는 시간이 가장 짧은 Job을 선택 하는 욕심쟁이 방법론이 적용이 가능합니다.

이번 문제는 이러한 욕심쟁이 방법론을 구현하기 위해서 Heap을 사용합니다.

 

이번 문제의 풀이순서는.

1. 가장 빨리 완료되는 init_job을 선택

2. init_job 이후에 바로 시작이 가능한 job을 탐색

3. 조건에따라

3_1. 2에서 시작 가능한 job이 있을 경우 이중 가장 짧은 처리시간이 걸리는 job을 init_job으로 선정

3_2. 2에서 시작 가능한 job이 없을 경우 가장 빠르게 시작 가능한 job을 init_job으로 선정

4. job더이상 수행할 job이 없을때까지 반복

 

이때 2번에서 구한 job들에서 처리시간이 가장짧은 job을 3_1에서 사용하게 됩니다.

 

단순히 List를 채우고, Max or Min을 사용하여도 가능은 합니다.

 

하지만! Max나 Min은 O(n)의 시간이 소요되기 때문에 시간초과가 발생합니다

 

이때 Heap을 사용할 경우, Element가 추가될때 O(logn)의 시간복잡도로 최대&최소값을 구할 수 있습니다.

 

아래는 Python을 사용해서 구해본 해당 문제의 Solution입니다

import heapq
import math
def solution(jobs):    
    answer = 0
    #이전 job의 완료시간을 기억하기 위한 변수
    bfe_time = 0
    job_count = len(jobs)
    #heap을 운용한 Array
    heap = []
    #pop()의 경우 log(1)의 시간이 걸리기 때문에
    #pop()를 사용하기 위해서 jobs를 뒤집어줍니다
    jobs = sorted(jobs, key = lambda x: (-x[0], -x[1]))
    #Event처리시간 기준으로 Heap이 생성되게 하기 위해서
    #Element의 순서를 뒤집어줍니다.
    jobs = [[i[1],i[0]] for i in jobs]    
    cur_job = jobs.pop()        
    while True:
        #반복문 중 jobs의 길이가 바뀌기 때문에
        #미리 해당 Value를 저장해줍니다.
        temp = len(jobs)        
        for i in range(temp):            
            #jobs의 시작시간이 이전 job의 완료시간 이전인 경우를 찾아
            #heap에 저장합니다.
            if jobs[temp-1-i][1]<=cur_job[0]+bfe_time:
                heapq.heappush(heap,jobs.pop())                    
            elif jobs[temp-1-i][1]>cur_job[0]+bfe_time:
                break                 
        #job의 시작시간이 이전 job의 완료시간보다 빠른경우
        #answer를 최신화하고, job 완료시간을 최산화해줍니다.
        if bfe_time>cur_job[1]:
            answer += (cur_job[0]+bfe_time-cur_job[1])
            bfe_time = cur_job[0]+bfe_time
        #job의 시작시간이 이전 job의 완료시간 이후인 경우
        else:
            answer += (cur_job[0])
            bfe_time = cur_job[0]+cur_job[1]        
        if len(jobs)==0 and len(heap)==0:
            break
        #바로 시작할 작업이 없는경우
        if len(heap)==0:
            cur_job = jobs.pop()            
        #바로 시작할 작업이 있는경우
        else:                        
            cur_job = heapq.heappop(heap)                       
    return math.floor(answer/job_count)