프로그래머스 코딩테스트 고득점 Kit_힙_디스크 컨트롤러

문제 보러 가기 👈 클릭!

💡 풀이

✔ 풀이 방법

작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법
= 현재 시점에서 작업 할 수 있는 일 중, 가장 소요시간이 작은 일 부터 처리

가장 먼저 요청 된 작업이 맨 뒤에 오도록 내림차순 정렬
=>jobs를 pop()하면 가장 맨 뒤에 있는 작업을 꺼내기 때문.

""
현재시점(end)에서 처리 할 수 있는 작업들을 jobs에서 꺼내서 최소힙 자료구조에 추가. =>현재 시점에서 처리 할 수 있는 작업 조건 = 현재시간 또는 현재시간 전에 요청 된 일

최소힙 자료구조에 일이 있다면 pop()하여 가장 작은 소요시간을 갖는 일부터 처리,
없다면 현재시간을 +1하며 새로운 일이 들어오길 기다린다.
""

다음 "" ""에 있는 과정들을 완료 하는 일의 개수가 총 일의 개수와 같을때까지 반복한다. => 해당 부분은 '완료해야할 일의 개수' = '총 일의 개수' 로 정의하고, 일을 처리할때마다 '완료해야할 일의 개수'을 1씩 감소시켜 0이 될때까지 반복하는 코드로 구현했음.

구현 코드👇

import heapq
def solution(jobs):
    #제일 먼저 요청 된 작업이 맨 뒤에 오도록 내림차순 정렬
    jobs.sort(reverse = True)
    
    N = len(jobs)   #총 작업의 개수
    cmplete_N = N   #완료 해야 할 작업의 개수
    
    start, end = -1, 0  #작업 시작 시간, 작업 완료 시간
    hq, sum_t = [], 0   #heap자료구조 , 소요시간 총 합
    while cmplete_N: #전체 반복문은 완료된 작업이 N개일때 종료 
        #현재 시점에서 처리 할 수 있는 작업들을 heap에 추가하는 과정
        while jobs:
            if jobs[-1][0] <= end:
                rq_time, size = jobs.pop()  #요청시간, 소요시간
                heapq.heappush(hq, (size, rq_time))
            else:
                break
        #heap에 담긴 작업 수행 => 가장 작은 소요시간을 가진 작업 먼저 수행
        if hq:
            size, rq_time = heapq.heappop(hq)  #소요시간, 요청시간
            start = end           #다음 직업 시작 시간 = 이전 작업 완료 시간
            end = start + size  #다음 작업 완료 시간 = 작업 시작 시간 + 소요시간
            sum_t += end - rq_time  #작업 끝나는 시간 - 작업 요청 시간
            cmplete_N -= 1                 #작업을 완료할 때마다 1씩 감소
        else:
            end += 1              #종료시간을 1씩 증가시키며 새로운 일이 들어오길 기다림
            
    return sum_t // N