프로그래머스 상담원 인원

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

프로그래머스

 

문제를 푸는 방법은 간단하다

1. 멘토 배정의 조합을 구한다 -> itertools.combinations 사용

2. 해당 조합으로 heapq 를 사용하여 순회한다 -> heapq push, pop

3. 조합 돌리면서 최소의 시간을 구한다

 

import heapq
from itertools import combinations

def calculate_wait_time(mentor_distribution, reqs):
    queues = {i: [] for i in range(1, len(mentor_distribution) + 1)}
    
    for i, count in enumerate(mentor_distribution, 1):
        # 주제: [0 for in 멘토수] 으로 초기화 -> 모든 주제의 각 멘토는 0부터 시작 가능
        # e.g) 조합 -> [1,2,3] -> {1: [0], 2: [0,0], 3:[0,0,0]}
        queues[i] = [0 for _ in range(count)]
        
    
    wait_time_sum = 0
    
    for request in reqs:
        a, b, c = request  # 시각 a, 상담 시간 b, 상담 유형 c
        end_time = heapq.heappop(queues[c])
        start_time = max(end_time, a)
        wait_time_sum += (start_time - a)
        heapq.heappush(queues[c], start_time + b)
    
    return wait_time_sum

def find_optimal_distribution(k, n, reqs):
    min_wait_time = float('inf')
    
    # 가능한 멘토 분배 조합을 모두 탐색
    combs = combinations(range(n-1), k-1)
    for comb in combs:
        distribution = [0] * k
        last = 0
        for i, v in enumerate(comb):
            distribution[i] = v + 1 - last
            last = v + 1
        distribution[-1] = n - last
        print(f"{comb} | {distribution}")
        
        wait_time = calculate_wait_time(distribution, reqs)
        min_wait_time = min_wait_time if min_wait_time < wait_time else wait_time
    
    return min_wait_time
def solution(k, n, reqs):
    answer = 0
    answer = find_optimal_distribution(k,n,reqs)
    return answer

 

combinations 를 지금까지 몰랐던 내가 한심해지는 순간이다