상담원 인원
문제 설명
- 상담 참가자와 멘토가 있다.
- 상담에는 유형이 있어서 멘토는 자신이 맡은 유형의 상담만 할 수 있다.
- 상담 요청에는 시간, 상담 시간, 상담 유형이 있다.
- 앞에 상담 받는 사람이 늦게 끝나면 뒤에 상담 받는 사람은 기다려야 한다.
최소 대기 시간을 구하라
흐름 파악
흐름 파악을 위해 꼬리에 꼬리를 무는 방식으로 접근하려한다.
최소 대기 시간을 구하려면 어떻게 해야할까?
멘토를 적절히 배정해야해
멘토를 적절히 배정하려면 어떻게 해야할까?
유형 별로 각 멘토 1명씩 배정한 후 한 명씩 추가 배정해보자
대기 시간은 어떻게 계산하지
예를 들어 멘토가 1명일 때 대기 시간을 계산해보자.
- 시작 시간 5분, 상담 시간 60분 유형 1
- 시작 시간 20분, 상담 시간 30분 유형 1
- 시작 시간 50분, 상담 시간 40분 유형 1
- 시작 : 5분 , 종료 : 5 + 60분
- 시작 : 65분, 종료 : 65 + 30분
- 시작 : 95분, 종료 : 95 + 40분
즉 각 상담 종료 시간을 큐에 넣고, 상담 요청이 들어올 때마다 큐에서 가장 빨리 끝나는 시간을 뽑아서 대기 시간을 계산하면 된다.
시행착오
맨 처음에는 각 유형 별 멘토 1명씩 배정을 해서 계산을 했다. 그 후 대기 시간이 가장 긴 유형에 멘토 1명씩 추가 배정하였다. 이렇게 했더니 100점 중에서 75점이 나왔다. 어디서 문제일까 생각하다보니 이 논리가 틀렸다는 것을 깨달았다.
대기 시간이 가장 많아 멘토 1명을 추가 배정하는 것이 다른 유형 멘토를 추가헀을 때보다 대기 시간이 줄었을 것이라는 보장이 없기 때문이다. 사실 여기서 발전했으면 금방 풀었을텐데 아예 딴길로 새어 BFS 방식으로 접근하였다. 그랬더니 테스트 케이스 한 6개 정도 빼고는 다 시간초과가 나왔다.
더 고민을 하다보니 멘토 한 명 늘렸을 때 경우를 다 구해서 가장 많이 대기 시간이 줄어든 유형에 멘토를 추가하면 되겠다는 생각이 들었다.
전체 코드
from collections import deque, defaultdict
def solution(k, n, reqs):
answer = 0
min_wait_time = None
reqs_by_kind_dict = defaultdict(list)
for req in reqs:
reqs_by_kind_dict[req[2]].append(req)
def calc_wait_time(kind, mentor_n):
waiting_time = 0
reqs_by_kind = deque(reqs_by_kind_dict[kind])
if not reqs_by_kind:
return 0
q = deque([])
while reqs_by_kind:
req = reqs_by_kind.popleft()
if len(q) < mentor_n:
q.append(req[0] + req[1])
continue
q = sorted(q, reverse=True)
cur_time = max(q[-1], req[0])
waiting_time += max(cur_time - req[0], 0)
q.pop()
q.append(cur_time + req[1])
return waiting_time
mentor_dict = {kind + 1: 1 for kind in range(k)}
if sum(mentor_dict.values()) == n:
wait_time_dict = {k: calc_wait_time(k, v) for k, v in mentor_dict.items()}
return sum([v for v in wait_time_dict.values()])
while sum(mentor_dict.values()) < n:
wait_time_possible_dict = defaultdict(int)
for i in range(1, k + 1):
mentor_copy = mentor_dict.copy()
mentor_copy[i] += 1
wait_time_dict = {k: calc_wait_time(k, v) for k, v in mentor_copy.items()}
wait_time_possible_dict[i] = sum([v for v in wait_time_dict.values()])
mentor_key = sorted([v for v in wait_time_possible_dict.items()], key=lambda x: x[1])[0][0]
if min_wait_time is None:
min_wait_time = wait_time_possible_dict[mentor_key]
elif min_wait_time > wait_time_possible_dict[mentor_key]:
min_wait_time = wait_time_possible_dict[mentor_key]
mentor_dict[mentor_key] += 1
return min_wait_time
print(solution(2, 3, [[5, 55, 2], [10, 90, 2], [20, 40, 2], [50, 45, 2], [100, 50, 2]]), 90)
print(solution(3, 3, [[0, 5, 1], [19, 5, 2], [20, 15, 3], [30, 40, 2], [30, 40, 1]]), 0)
print(solution(3, 5, [[10, 60, 1], [15, 100, 3], [20, 30, 1], [30, 50, 3], [50, 40, 1], [60, 30, 2], [65, 30, 1],
[70, 100, 2]]), 25)
print(solution(2, 3, [[0, 100, 1], [5, 100, 2], [10, 100, 1], [15, 30, 2], [20, 100, 1], [45, 10, 2], [60, 5, 2]]), 270)
print(solution(2, 2, [[0, 5, 1], [19, 5, 2], [20, 15, 2], [30, 40, 2], [30, 40, 1]]), 13)
print(solution(2, 2, [[0, 5, 1], [10, 5, 2], [20, 15, 2], [30, 40, 2], [30, 40, 1]]), 5)
print(solution(2, 2, [[0, 5, 2], [10, 5, 2], [20, 15, 2], [30, 40, 1]]), 0)
print(solution(2, 2, [[0, 5, 2], [10, 5, 2], [20, 15, 2], [30, 40, 2]]), 5)
print(solution(2, 2, [[0, 5, 2], [10, 5, 2], [20, 11, 2], [30, 40, 2]]), 1)
print(solution(2, 2, [[5, 5, 2], [10, 5, 2], [20, 11, 2], [30, 40, 2]]), 1)
print(solution(2, 3, [[5, 5, 2], [10, 5, 2], [20, 11, 2], [30, 40, 2]]), 0)
print(solution(2, 3, [[5, 5, 2], [10, 5, 2], [20, 5, 2]]), 0)
print(solution(2, 3, [[5, 5, 2], [10, 5, 2], [20, 5, 2], [30, 40, 2]]), 0)
print(solution(2, 3, [[5, 5, 2], [10, 5, 2], [20, 10, 2], [30, 40, 2]]), 0)
