[프로그래머스] 2023 현대모비스 상담원 인원

문제

상담유형 k개, 상담원 n명이 있을 때 주어진 참여자들의 대기시간이 가장 짧게 상담원을 배치하고, 그 때의 대기시간을 구해라.
단, 상담유형마다 최소 1명의 상담원은 배치되어야 한다.

ex)

reqs = [
	# [시작시간, 소요시간, 상담유형]
	[10, 60, 1], 
    [15, 100, 3], 
    [20, 30, 1], 
    [30, 50, 3], 
    [50, 40, 1], 
    [60, 30, 2], 
    [65, 30, 1], 
    [70, 100, 2]
]
k, n = 3, 5

처음에는 최소시간을 가지는 조건을 찾아야하는건가? 라는 생각을 하다가 도저히 생각이 나지 않았다. 이후에 경우의 수가 그렇게 많지 않길래 모든 경우에 대해 대기시간을 구해 비교하기로 했다.

우선, k, n = 3, 5를 예시로 설명하겠다.
[사용안함, 1, 1, 1] => 이런식으로 1명씩은 배치되어야 한다.
나머지 2명은 1,2,3번 중에 선택하면된다. 즉, 중복조합 $_3H_2$을 하면된다.

# 중복조합
import itertools

totalCase = []
defaultArrange = [1 for _ in range(k + 1)] # 1번 인덱스부터 쓰기위해
# combinations_with_replacement가 중복조합임
for row in itertools.combinations_with_replacement([i for i in range(1, k + 1)], n - k):
	totalCase.append(defaultArrange[:])
    for typeNum in row:
    	totalCase[-1][typeNum] += 1
        
# [X, 1, 1, 1]를 기준으로 남은 상담원이 뽑은 유형번호의 값을 증가시킴

이제 [1, 1, 3], [1, 2, 2]에 대해서 생각해보자.
필자는 각 상담유형의 번호를 키 값으로 가지는 리스트를 만들고 상담원 수만큼 0을 추가해줬다.

for eachCase in totalCase:
        room = {}
        for i in range(1, k + 1):
            room[f'{i}'] = []
            for j in range(eachCase[i]):
                room[f'{i}'].append(0) # 끝나는시간
                
# [1, 1, 3]일 때 room -> {'1': [0], '2': [0], '3': [0, 0, 0]}
# [1, 2, 2]일 때 room -> {'1': [0], '2': [0, 0], '3': [0, 0]}

이제 각 유형별 리스트에 대해 heapq를 이용할 것이다.
참가자별 대기시간을 다음과 같이 구할 것이다.

1. 참가자가 희망하는 유형의 리스트에서 heappop으로 꺼내온다.
   -> 끝나는시간으로 넣을 것이기 때문에 가장 빨리 끝나는 방이 나온다.
2. 끝나는시간이 현재 참가자의 시작시간보다 앞이면 기다리지 않는다.
3. 끝나는시간이 현재 참가자의 시작시간보다 뒤면 (끝나는시간 - 시작시간) 기다린다.

나머지 설명은 코드 주석을 통해 하겠다.

전체코드

import sys
import heapq
import itertools

def solution(k, n, reqs):
    totalCase = []
    defaultArrange = [1 for _ in range(k + 1)] # 1번 인덱스부터 쓰기위해
    for row in itertools.combinations_with_replacement([i for i in range(1, k + 1)], n - k):    #중복조합
        totalCase.append(defaultArrange[:])
        for typeNum in row:
            totalCase[-1][typeNum] += 1

    answer = sys.maxsize
    for eachCase in totalCase:
        room = {}
        for i in range(1, k + 1):
            room[f'{i}'] = []
            for j in range(eachCase[i]):
                room[f'{i}'].append(0) # 끝나는시간

        waitingTime = 0
        for startTime, duration, typeNum in reqs:
            prevEndTime = heapq.heappop(room[f'{typeNum}'])
            

            if prevEndTime <= startTime:    # 기다림 X
                heapq.heappush(room[f'{typeNum}'], startTime + duration)    # 현재참가자기준 끝나는시간 heappush
            else:                           # 기다림 O
                waitingTime += (prevEndTime - startTime)
                heapq.heappush(room[f'{typeNum}'], prevEndTime + duration)  # 현재참가자기준 끝나는시간 heappush
            
            # 이미 최소대기시간을 넘어버리면 스킵
            if waitingTime >= answer:
                break
        
        answer = min(answer, waitingTime)

    return answer