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

문제 설명

 

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

 

 

나의 솔루션

 

수식을 만들어 활용하면 쉽게 풀 수 있는 문제였다. (다만 공식을 알아내기까지 시간이 다소 걸렸다) 이 문제의 핵심은 평균 시간을 최대한 줄이는 것이었기 때문에, 평균의 특징을 잘 생각해보며 접근했다. 

 

평균을 낮출 수 있는 가장 좋은 방법은 원 데이터 각각의 값을 낮출 수 있는 만큼 낮추는 것이다. 평균은 숫자들이 밀집되어 있는 값이 추출된 것이기 때문에, 데이터가 하나라도 어마어마하게 큰 값을 갖게 된다면 평균 역시 그만큼 높아지게 된다. 

 

jobs 배열에는 하나의 작업이 요청되는 시점과 해당 작업에 소요되는 시간들의 집합이 담겨있다. 작업이 요청되는 시점에 즉시 실행되면 작업 시간은 최소화 될 것이며, 작업이 시작되는 시간이 뒤로 밀릴수록 총 작업 시간이 늘어날 것임은 당연하다. 따라서 모든 작업이 요청 시간과 최대한 근접한 시간에 실행될 수 있도록 일찍 들어온 요청부터 순차적으로 처리하여 작업 시간을 계산하는 코드를 작성했다. 

 

import heapq

def solution(jobs):
    result = []
    heapq.heapify(jobs)
    time = jobs[0][0] 
    
    while True:
        
        if len(jobs) == 0:
            break

        if jobs[0][0] > time:  
            first = heapq.heappop(jobs)
            time = first[1] + first[0]
            
        else:
            new_jobs = list(filter(lambda x : x[0] <= time, jobs))
            new_jobs.sort(key = lambda x: (x[1],-x[0]))  
            first = new_jobs[0]
            time += first[1] 
            jobs.remove(first)

        result.append(time-first[0])       

    return sum(result) / len(result)