[자료구조] [heap] 대기 시간 최소화

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

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

Minimum Average Waiting Time | HackerRank

 

문제는 다음과 같다. 피자 가게에서 고객들의 대기시간을 최소화하는 것을 목표로 평균 대기시간을 구하는 것이다. 피자 만드는 시간은 각기 다르며, 주문이 들어올 때, 선입선출(First in, First out)에 기반하여 주문을 처리하지 않는다. 

문제에서 input으로 들어오는 것은 [고객이 주문하는 시간, 피자 만드는데 걸리는 시간]으로 구성된 list이다.

ex) input = [[0,3],[1,9],[2,6]] 

그리고 제약조건에 있어서 list의 길이는 최대 10만개이다. 

문제를 이해하기 위해서 시각화한 그림은 다음과 같다. 이번 문제에서는 특히, 문제를 풀기 위한 아이디어를 코드화하는데 어려움이 있었다. (노란색 마킹한 부분, 특정 고객의 주문을 처리하면서 발생하는 대기 고객들을 어떻게 한정짓느냐였다.) 그리고 지금까지 만드는 피자를 요리하는데 소요되는 시간들을 어떻게 표현하면서 추가적으로 밀려들어오는 고객들을 다음 번째 대기자 후보로 결정할 것인지가 문제였다.

 먼저, 아직 처리하지 않은 대기자들만을 customer 목록에 포함하기로 하였으며, 이들을 처리하고자 하면 customers.pop(0)으로 뽑았다. (=> 하지만 pop(0)의 경우 time complexity가 O(N)이다). 이중 while문으로 위에 아이디어를 구체화 하였다.

1) 가장 크게 감싸는 while 조건문은 customers에 대기자가 있거나 혹은 우선순위큐에 해당하는 heap에 원소가 있는 경우이다. 두 자료형에 아무것도 없을 경우 우리는 모든 대기자들을 처리했으므로, 정답을 return 하면 된다.  

2) 다음으로, customers에 인자가 존재하고, customers에 있는 첫번째 대기자가 우리가 현 타이밍에 제조하고 있는 피자를 만들때에 대기하고 있는 고객이거나 혹은 candi에 인자가 없을 경우(지금까지 pizza를 만드는데 있어서 대기자들을 모두 처리했다는 의미이므로) candi라는 힙 자료구조에 튜플(pizza소요시간, 고객이 도착한 시간 타임)을 인자를 넣는다. 소 while문은 candi에 인자가 있거나 현 customer목록의 첫번째 인자가 지금까지 걸린 피자 제조시간보다 크다면 작동하지 않는다.

그리고 지금까지 피자를 만드는데 소요되는 시간을 측정하는 time을 넣는다. 이후에는 candi 힙 자료구조에 남아있는 인자들 중 피자만드는 시간이 가장 적은 것을 뽑아서 time에 넣고, 여기서 피자집에 당도한 시간을 빼서 총 wait_time에 넣는다. 

위와 관련된 코드는 다음과 같다.

대기시간 문제는 어려우면서, 도전해볼만큼 흥미로운 것 같다. 다시 한 번 복기할거다.

def minimumAverage(customers):
    #
    # Write your code here.
    #
    # customers에는 고객이 도착한 시간과, 그들이 주문한 피자의 소요시간이 나타나진다. 
    customers.sort()
    time = 0
    wait_time = 0
    candi = []
    N = len(customers)
    #customers에 값이 있거나 혹은 candi에 값이 있는 경우
    while customers or candi :
        #customers에 값이 있고, 
        #candi에 값이 없거나, customer에 남아 있는 값들이 time보다 적을 때)
        while customers and (not candi or customers[0][0]<= time):
            arrive, pizza = customers.pop(0)
            hq.heappush(candi, (pizza, arrive)) #pizza 조리 시간이 가장 적은 것을 선택하기 위해서, heapq사용하였다. 
            time = max(time, arrive)

        pizza, arrive = hq.heappop(candi) #candi에 있는 것 중에서 가장 적은 pizza선택
        time += pizza
        wait_time += time-arrive
    
    return wait_time//N