[자료구조] [python] [heapq] Minimum Average Waiting Time

다음의 문제는 heapq을 활용해서 푸는 문제에 해당한다.  

Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 

www.hackerrank.com/challenges/minimum-average-waiting-time/problem

Minimum Average Waiting Time | HackerRank

 

풀이 로직은 다음과 같다. 일단 어떤 작업이 끝난 시점에, 들어온 작업들 중에서 가장 작업량이 적은 주문을 선택해야, 전체의 평균 대기 시간을 줄일 수 있다.

 

1) 특정 시점에 들어온 작업들 중에서 가장 작업량이 적은 주문을 선택하기 위해서 heapq 자료형을 사용한다.

2) 특정인의 대기 시간의 총 합을 구하기 위한 프로세스는 다음과 같다. 아래 사진에서 두 번째 사람의 대기시간 (연보라 + 보라 + 진한 보라) 의 시간을 구하기 위해서, 특정인이 가게에 도착한 시간 정보(1초)와 작업량이 끝난 시점(17초)를 빼서 총 대기 시간 정보에 더한다. 

 

 

import os
import heapq, sys

def minimumAverage(customers, n):
    heapq.heapify(customers)
    
    time = 0
    total_time = 0
    queue = []
    
    while customers or queue :
        
        while customers and (not queue or customers[0][0]<=time):
            next_one = heapq.heappop(customers)
            heapq.heappush(queue, [next_one[1],next_one[0]])
            time = max(next_one[0], time)
        
        L, T = heapq.heappop(queue)
        time += L
        total_time += time - T
        
    
    return (total_time // n)