[2023 현대모비스 알고리즘 경진대회 예선] 상담원 인원

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

프로그래머스

꽤 빡구현 문제지만, 파이썬은 내장 라이브러리로 꽤 많은 부분을 해결할 수 있어서 어렵지 않다. 
deque, itertools, heapq 등을 모두 동원해야 풀 수 있는 문제.
물론 itertools를 쓰는 것 보다 좀 더 효율적인 방법이 있지만..
가독성 및 코딩 시간 단축을 위해 내장 라이브러리를... 

from collections import deque
from itertools import product
from heapq import heappush, heappop


def solution(k, n, reqs):
    def calculate_waiting_time(_mentors_nums):
        waiting_time = 0
        for request, mentors_num in zip(requests, _mentors_nums):
            queue = deque(sorted(request))
            mentor_end_times = [0] * mentors_num
            while queue:
                _t, _d = queue.popleft()
                min_end_time = heappop(mentor_end_times)
                if min_end_time <= _t:
                    heappush(mentor_end_times, _t + _d)
                else:
                    waiting_time += min_end_time - _t
                    heappush(mentor_end_times, min_end_time + _d)
        return waiting_time

    requests = tuple([] for _ in range(k))
    for t, d, c in reqs:  # 시각, 상담 시간, 상담 유형
        requests[c - 1].append((t, d))
    min_waiting_time = float('inf')
    for mentos_nums in product(range(1, n - k + 2), repeat=k):
        if sum(mentos_nums) == n:
            min_waiting_time = min(min_waiting_time, calculate_waiting_time(mentos_nums))
    return min_waiting_time