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

프로그래머스

 

각 상담 유형에 적절하게 담당 멘토를 배치해서 참가자들의 대기 시간을 최소화 하는 문제입니다.

 

제공되는 파라미터들의 범위가 크지 않으므로 완전탐색을 이용해 보겠습니다.

 

순서는 다음과 같습니다.

 

1. 멘토 배치가 가능한 경우의 수 모두 생성
2. 각 경우의 수 마다 발생하는 대기시간 계산
3. 최소의 대기시간을 구하여 반환

 

---

 

우선 첫번째, 배치 가능한 경우의 수를 생성합니다.

from itertools import product

for mento_distribute in product(range(1, n+1), repeat=k):
        if sum(mento_distribute) == n:
            waiting_time = check_time(mento_distribute, k, reqs)
            answer = min(answer, waiting_time)

Python / Itertools Product / 카테시안 곱

[1 ~ n] 객체를 repeat = 3 하도록 product 했다고 가정해보면

 

ex) [1, 2, 2] = 1번 유형: 1명 | 2번 유형: 2명 | 3번 유형: 2명

       [3, 1, 1] = 1번 유형: 3명 | 2번 유형: 1명 | 3번 유형: 1명

 

라고 해석할 수 있습니다.

 

총 멘토가 n명이 있었으므로 product 객체 내의 수는 그 합이 n이 되어야 합니다.

 

그러므로 product의 총 합, sum(product 객체) == n 인 경우에만 취급합니다.

 

이렇게 생성된 멘토 배치의 경우의 수를 가지고 대기 시간을 계산해주겠습니다.

 

 

---

 

import heapq

def check_time(mento_distribute, k, reqs):
    mento = []
    waiting = 0
    
    for n in mento_distribute:
        mento.append([0 for x in range(n)])
        
    for s, f, num in reqs:
        time = heapq.heappop(mento[num-1])
        waiting += max(0, time-s)
        heapq.heappush(mento[num-1], max(s, time)+f)
    
    return waiting

mento 리스트는 현재 활동중인 멘토들이 상담이 끝나는 시간을 저장해줄 공간입니다.

 

이 때 끝나는 시간의 최소값을 빠르게 구할 필요가 있으므로 heapq의 형태를 사용해 주겠습니다.

Python / 힙 자료구조 / heapq

초기에는 아직 멘토가 활동중이지 않다고 가정하고 각 유형마다 배정된 멘토의 수 만큼 0으로 초기화 해주겠습니다.

ex) [1, 2, 2] => [0]         => 1번 유형

                             [0, 0]     => 2번 유형

                             [0, 0]     => 3번 유형

 

이제 상담 요청 리스트로부터 요청을 한 개씩 꺼내와서 상담사를 배치해 주겠습니다.

 

각 유형에 해당하는 멘토들 중 가장 먼저 상담이 끝나는 상담사를 찾습니다.

 

이 때 mento 리스트에 저장된 값이 가장 작은 (= 상담이 가장 일찍 끝나는)값을 heappop 함수로 꺼내와 줍니다.

 

만약 그 값이 현재 상담을 요청한 사람이 도착한 시간, s 보다 크다는 것은 대기시간이 발생한다는 의미입니다.

 

만약 대기시간이 발생한다면 (상담 끝나는 시간 - 도착시간)을, 아니라면 0을 총 대기시간에 더해줍니다.

 

이제 요청자가 상담을 받는다고 가정하고 상담이 끝나는 시간을 새롭게 계산해서 mento 리스트에 넣어줄 것입니다.

 

새로운 상담 종료 시간은 (상담 시작 시간 + 상담 소요 시간)이 될 것입니다.

 

상담 시작 시간은 요청자가 도착한 시간과 상담자가 상담이 끝나는 시간 중 더 큰 값이 들어가게 됩니다.

 

heappush를 사용하여 다시 mento리스트에 상담이 끝나는 시간을 넣어줍니다.

 

이를 모든 요청동안 반복한 뒤 마지막에 쌓인 대기시간 waiting을 반환해줍니다.

 

---

전체 코드

import heapq
from itertools import product

def check_time(mento_distribute, k, reqs):
    mento = []
    waiting = 0
    
    for n in mento_distribute:
        mento.append([0 for x in range(n)])
        
    for s, f, num in reqs:
        time = heapq.heappop(mento[num-1])
        waiting += max(0, time-s)
        heapq.heappush(mento[num-1], max(s, time)+f)
    
    return waiting
    
def solution(k, n, reqs):
    answer = float("inf")
    
    for mento_distribute in product(range(1, n+1), repeat=k):
        if sum(mento_distribute) == n:
            waiting_time = check_time(mento_distribute, k, reqs)
            answer = min(answer, waiting_time)
    
    return answer