🐹 상담원 인원

1. 문제 링크

상담원 인원

2. 코드

from itertools import product
from collections import deque

def check_consult_finish(consult_list, now_category, req_time):
    c_list = consult_list.copy()
    finish = 0
    while c_list:
        end_time, category = c_list.popleft()
        # 이전 상담유형의 모든 상담 마무리 -> 상담 내역 없애기 
        if category != now_category:
            return (0, deque([]))
        # 현재 시점에서 이미 끝난 상담 확인
        if end_time <= req_time:
            finish += 1
            continue
        break
    
    cnt = finish
    while cnt:
        cnt -= 1
        consult_list.popleft()

    return (finish, consult_list)

def solution(k, n, reqs):
    # 멘토 n명
    mentor = range(1, n+1)
    reqs.sort(key=lambda x: x[2])

    # k개의 유형으로 나누는 모든 경우의 수 구하기 (중복순열)
    consulting_permutations = [p for p in product(mentor, repeat=k) if sum(p) == n]
    
    min_value = int(1e9)
    # 멘토 상담 배치 모든 경우
    for c in consulting_permutations:
        waiting = 0
        mentors = list(c)
        consult_list = deque([])
        for req in reqs:
            req_time, consult_time, category = req
            # 가장 빨리 끝나는 순으로 대기
            consult_list = deque(sorted(consult_list, key=lambda x: x[0]))
            # 멘토 상담 끝났으면 돌려놓기
            cnt, c_list = check_consult_finish(consult_list, category, req_time)
            mentors[category-1] += cnt
            consult_list = c_list
            # 배정할 멘토가 있을 시(상담 바로 가능)
            if mentors[category-1] > 0:
                mentors[category-1] -= 1
                consult_list.append((req_time + consult_time, category)) # 상담 배정
            # 배정할 멘토가 없을 시(대기 필요)
            else:
                end_time, category = consult_list.popleft()
                waiting += end_time - req_time
                consult_list.append((end_time + consult_time, category)) # 상담 배정
            
        min_value = min(min_value, waiting)

    return min_value

테스트 1 〉	통과 (0.03ms, 10.5MB)
테스트 2 〉	통과 (0.04ms, 10.4MB)
테스트 3 〉	통과 (0.04ms, 10.3MB)
테스트 4 〉	통과 (0.05ms, 10.4MB)
테스트 5 〉	통과 (1.47ms, 10.1MB)
테스트 6 〉	통과 (20.61ms, 10.3MB)
테스트 7 〉	통과 (6.40ms, 10.3MB)
테스트 8 〉	통과 (0.80ms, 10.3MB)
테스트 9 〉	통과 (1935.87ms, 10.6MB)
테스트 10 〉	통과 (2103.60ms, 10.6MB)
테스트 11 〉	통과 (1921.13ms, 10.6MB)
테스트 12 〉	통과 (1881.78ms, 10.5MB)
테스트 13 〉	통과 (1908.63ms, 10.5MB)
테스트 14 〉	통과 (2061.11ms, 10.5MB)
테스트 15 〉	통과 (2001.30ms, 10.5MB)
테스트 16 〉	통과 (1968.97ms, 10.5MB)
테스트 17 〉	통과 (1956.36ms, 10.5MB)
테스트 18 〉	통과 (2097.11ms, 10.6MB)
테스트 19 〉	통과 (2034.02ms, 10.7MB)
테스트 20 〉	통과 (1925.74ms, 10.5MB)

3. 해설

product(중복 순열)을 사용하여 각 상담 유형에 멘토를 배치하는 모든 경우 consulting_permutations를 구한다. 각 상담 유형별로 계산하기 위해 req를 상담 유형순으로 정렬한다. 그 후 다음과 같은 연산을 한다.

1. 현재 상담 리스트((끝나는 시간, 상담 유형) 형식 큐)에 등록되어 있는 경우를 상담이 빨리 끝나는 순으로 정렬한다.

2. 상담이 끝난 멘토는 대기 자리에 돌려놓는다(상담 유형(i)에 해당하는 mentors[i]에 1을 더해줌)

   이때, 만약 상담 유형이 현재 확인하는 상담 유형과 다르면(이전 번호 상담이 모두 끝났다면) 큐를 비워준다.

3. 상담 대기 유무를 파악한다

   1. 상담 바로 가능 → mentors[i]가 0 보다 크다(상담 가능한 멘토가 남아있다)

      이때는 멘토 수를 하나 줄인다.

      끝나는 시간 = 상담 요청시각 + 상담 시간으로 초기화하여 상담 리스트에 넣어준다.

   2. 상담 대기 필요 → mentors[i]가 0일 때(상담 가능한 멘토가 없음)

      대기 후 바로 다음 멘토로 넘기기 때문에 멘토 수는 그대로 놔둔다.

      기다린 시간 = 이전 상담 끝나는 시간 - 상담 요청 시각 으로 총 대기 시간에 더해준다.

      끝나는 시간 = 이전 상담 끝나는 시간 + 상담 시간으로 초기화하여 상담 리스트에 넣어준다.

위의 연산을 마무리 했을 때 대기 시간의 최솟값을 리턴한다.