[프로그래머스] 상담원 인원 - Python

https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스

 

문제 유형 : 구현 + priority queue 활용하기 

import heapq 
from itertools import combinations_with_replacement
from collections import defaultdict 

def solution(k, n, reqs):
    answer = int(1e9) # 기다린 시간의 최솟값 

    type_list = defaultdict(list) # type 별로 분리하기 
    
    # 1.  n-k 명 멘토 할당하는 모든 경우의 수 구하기 
    comb = combinations_with_replacement([i for i in range(k)], r=n-k)  # 중복 허용한 nCr 
    cases = []
    for com in comb:
        temp = [1 for i in range(k)] # 각 유형당 1명씩 무조건 배치 
        for i in com:
            temp[i] += 1
        cases.append(temp)

    for i in range(len(reqs)):
        start, dur, t = reqs[i]
        type_list[t-1].append([start, dur+start])
	# 2. 경우의 수를 brute force 로 확인하면서 최소 대기 시간 구하기 
    for case in cases: 
        total = 0 
        # 3. type 별로 대기 시간 구하기 
        for i in range(k): 
            t_list = type_list[i]
            
            mento_list = [] # 4. 타입별로 priority queue 만들기 

            for _ in range(case[i]):
                heapq.heappush(mento_list, 0)
                
			# 5. mento 를 기다리는 경우 & 기다리지 않는 경우 나눠서 계산 
            for start, end in t_list:
                mento = heapq.heappop(mento_list) # mento가 있는 시간 
                
                if mento < start: # mento 가 available 한 경우 
                    heapq.heappush(mento_list, end)
                else: # mento 기다려야 하는 경우 
                    wait = mento - start
                    total += wait 
                    heapq.heappush(mento_list, end + wait)
                
   
        answer = min(answer, total)
    
    return answer