[99클럽/파이썬 챌린저/18일차] 상담원 인원

프로그래머스 상담원 인원 LV3

 

문제
현대모비스는 우수한 SW 인재 채용을 위해 상시로 채용 설명회를 진행하고 있습니다. 채용 설명회에서는 채용과 관련된 상담을 원하는 참가자에게 멘토와 1:1로 상담할 수 있는 기회를 제공합니다. 채용 설명회에는 멘토 n명이 있으며, 1~k번으로 분류되는 상담 유형이 있습니다. 각 멘토는 k개의 상담 유형 중 하나만 담당할 수 있습니다.
멘토는 자신이 담당하는 유형의 상담만 가능하며, 다른 유형의 상담은 불가능합니다. 멘토는 동시에 참가자 한 명과만 상담 가능하며, 상담 시간은 정확히 참가자가 요청한 시간만큼 걸립니다.
참가자가 상담 요청을 하면 아래와 같은 규칙대로 상담을 진행합니다.

상담을 원하는 참가자가 상담 요청을 했을 때, 참가자의 상담 유형을 담당하는 멘토 중 상담 중이 아닌 멘토와 상담을 시작합니다. 만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다립니다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간입니다. 모든 멘토는 상담이 끝났을 때 자신의 상담 유형의 상담을 받기 위해 기다리고 있는 참가자가 있으면 즉시 상담을 시작합니다. 이때, 먼저 상담 요청한 참가자가 우선됩니다.
참가자의 상담 요청 정보가 주어질 때, 참가자가 상담을 요청했을 때부터 상담을 시작하기까지 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원을 정하려 합니다. 단, 각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.


제한사항
1 ≤ k ≤ 5
k ≤ n ≤ 20
3 ≤ reqs의 길이 ≤ 300
reqs의 원소는 [a, b, c] 형태의 길이가 3인 정수 배열이며, c번 유형의 상담을 원하는 참가자가 a분에 b분 동안의 상담을 요청했음을 의미합니다. 1 ≤ a ≤ 1,000   1 ≤ b ≤ 100   1 ≤ c ≤ k, reqs는 a를 기준으로 오름차순으로 정렬되어 있습니다. reqs 배열에서 a는 중복되지 않습니다. 즉, 참가자가 상담 요청한 시각은 모두 다릅니다.

입출력 예

k	n	reqs	result
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
2	3	[[5, 55, 2], [10, 90, 2], [20, 40, 2], [50, 45, 2], [100, 50, 2]]	90
2	2	[[1, 10, 1], [2, 10, 1]]	9
1	1	[[0, 100, 1], [50, 100, 1], [200, 300, 1], [500, 100, 1]]	50
2	3	[[0, 100, 1], [5, 100, 2], [10, 100, 1], [15, 30, 2], [20, 100, 1], [45, 10, 2], [60, 5, 2]]	270

 

 

특정 유형에 사람을 한 명 추가했을 때 감소되는 상담대기시간이 큰 유형을 선택하는 탐욕적인 방법을 생각했다.

우선순위 큐를 사용해서 감소되는 양이 가장 큰 유형을 찾아냈다.

 

특정 유형의 상담 대기 시간 또한 우선순위 큐를 이용하여 구했다.

우선순위 큐에는 상담 종료 시간을 넣어두고, 개수가 상담 인원을 초과하지 않도록 조절하였다.

이를 함수로 따로 빼두어서 구하였다.

 

우선순위는 감소되는 양으로  (현재 상담원의 대기 시간)  - (현재 상담원 + 1명의 대기 시간)가 큰 순서로 뽑았다.

 

현재 상담원의 대기 시간이 큰 순서로 상담원을 주는 방식은 아래 케이스에서 통과하지 못한다.

 

2, 3, [[0, 100, 1], [5, 100, 2], [10, 100, 1], [15, 30, 2], [20, 100, 1], [45, 10, 2], [60, 5, 2]], 270

 

import heapq

def solution(k, n, reqs):
    
    routes = [[] for _ in range(k+1)]
    sangdam_cnts = [1] * (k+1)
    n -= k
    
    for s, t, ty in reqs: routes[ty].append([s, t])
    
    def find(i, cnt):
        wait_time = 0
        pq = []
        for s, t in routes[i]:                
            if cnt > 0:
                heapq.heappush(pq, s+t)
                cnt -= 1
                continue
            ft = heapq.heappop(pq)
            if ft <= s:
                heapq.heappush(pq, s+t)
                continue
            wait_time += ft-s
            heapq.heappush(pq, ft+t)
        return wait_time
    
    
    
    hq = []
    for i in range(1, k+1): heapq.heappush(hq, [find(i, 2)-find(i, 1), i])
    
    while n > 0:
        n -= 1
        t, i = heapq.heappop(hq)
        sangdam_cnts[i] += 1
        heapq.heappush(hq, [find(i, sangdam_cnts[i]+1)-find(i, sangdam_cnts[i]), i])
        
        
    answer = 0
    for i in range(1, k+1): answer += find(i, sangdam_cnts[i])
    return answer​

 

---