[프로그래머스] 상담원 인원(조합, heapq) LV3

 

https://school.programmers.co.kr/learn/courses/30/lessons/214288#

프로그래머스

사실 너무너무 어려워서 GPT 선생님과 함께 했다.. 다음에 꼭 다시 풀어보기🤙

🚩 풀이 과정

(1) 상담 유형별 멘토 배정 조합 생성

상담 유형 별로 유형별 멘토가 몇 명씩 배정될 것인지 경우의 수를 조합으로 모두 고려하였다.

예를 들어 1번 유형의 경우 

1. 5명의 멘토를 3가지 유형에 배정해야 하고

2. 한 유형에 반드시 1명의 멘토는 배정되어야 한다.

따라서 아래와 같은 조합이 나온다.

# k=3, n=5 일 경우
[[3, 1, 1], [2, 2, 1], [2, 1, 2], [1, 3, 1], [1, 2, 2], [1, 1, 3]]

 

이를 위해 아래와 같이 함수를 정의하였다.

from itertools import combinations_with_replacement

def generate_mentor(n,k):
    mentor_list = []
    base_mentor = [1] * k #최소 1명씩 배정
    remaining_mentor = n - k #추가로 배정할 인원
    
    
    #조합 생성
    for comb in combinations_with_replacement(range(k), remaining_mentor):
        print(comb)
        mentor = base_mentor[:] #깊은 복사
        for idx in comb:
            mentor[idx] += 1
        mentor_list.append(mentor)
    
    #print(mentor_list) [[3, 1, 1], [2, 2, 1], [2, 1, 2], [1, 3, 1], [1, 2, 2], [1, 1, 3]]
    return mentor_list

최소한명씩 배정 후 추가로 배정할 인원에 대해 조합 생성

생성된 조합을 돌면서 해당하는 index(상담 유형) 에 +1을 해주어 배정 경우의 수를 만들어 주었다.

 

(2) 상담 대기 시간 계산

배정한 상담원 인원 수 별로 대기 시간을 모두 구한 후에 가장 작은 대기 시간을 반환하였다.

이를 위해 아래와 같은 함수를 정의하였다.

import heapq

def calculate_wating_time(reqs, mentor_list, k):
    total_waiting_time = 0
    mentor_queues = {i:[] for i in range(1, k+1)} #각 유형별 멘토 큐 {1: [], 2: [], 3: []}
    
    #유형별 상담 진행
    for start, duration, type_id in reqs:
        queue = mentor_queues[type_id]
        
        if len(queue) < mentor_list[type_id - 1]: #상담가능한 인원이 남아있을 때
            heapq.heappush(queue, start + duration) #상담시작(상담 끝나는 시간 push)
        else: #모두 상담중일 때 -> 기다리는 시간 계산
            #우선순위큐로 상담이 가장 빨리 끝나는 멘토 꺼내기
            earliest_end = heapq.heappop(queue)
            wait_time = max(0, earliest_end - start)
            total_waiting_time += wait_time
            heapq.heappush(queue, max(earliest_end, start) + duration) #상담이 실제 끝나는 시간
    
    return total_waiting_time

1. 각 유형별로 멘토 큐를 만들어 준 후

2. 상담 가능한 인원이 남아 있을 경우엔 상담이 끝나는 시간을 push하고

3. 상담 가능한 인원이 남아 있지 않은 경우엔 기다리는 시간을 계산하였다.

4. 여기서 처음에 실수한 부분은,, 모두 상담 중일 때 기다리는 시간을 구한 후 heapq에 earliest_end + duration 을 넣어주었다. 하지만, 아래 2가지 경우를 고려하면 새로 들어온 요청의 상담 시작 시간과 이전 상담이 끝나는 시간 중 더 큰 값을 구해주어야 한다는 사실을 알게 되었다.

📌 CASE 1 : 기존 상담사가 끝나기 전에 새 요청이 들어온 경우

- 요청이 들어온 시간: 5

- 가장 빨리 끝나는 상담 종료 시간: 8

- 상담 지속 시간: 3

max(8, 5) + 3 = 11

 

📌 CASE 2 : 기존 상담이 끝나고 한참 뒤에 새로운 상담 요청이 들어온 경우

- 요청이 들어온 시간: 12

- 가장 빨리 끝나는 상담 종료 시간: 8

- 상담 지속 시간: 3

max(8, 12) + 3 = 15

따라서 heapq.heappush(queue, max(earliest_end, start) + duration) 이렇게 큐에 넣어주어야 실제 상담이 종료된 시간을 구할 수 있다!

 

(3) 모든 조합 별 상담 대기 시간 중 최소값 구하기(최종코드)

from itertools import combinations_with_replacement
import heapq

def generate_mentor(n,k):
    mentor_list = []
    base_mentor = [1] * k #최소 1명씩 배정
    remaining_mentor = n - k #추가로 배정할 인원
    
    
    #조합 생성
    for comb in combinations_with_replacement(range(k), remaining_mentor):
        print(comb)
        mentor = base_mentor[:] #깊은 복사
        for idx in comb:
            mentor[idx] += 1
        mentor_list.append(mentor)
    
    print(mentor_list)
    return mentor_list

def calculate_wating_time(reqs, mentor_list, k):
    total_waiting_time = 0
    mentor_queues = {i:[] for i in range(1, k+1)} #각 유형별 멘토 큐 {1: [], 2: [], 3: []}
    
    #유형별 상담 진행
    for start, duration, type_id in reqs:
        queue = mentor_queues[type_id]
        
        if len(queue) < mentor_list[type_id - 1]: #상담가능한 인원이 남아있을 때
            heapq.heappush(queue, start + duration) #상담시작(상담 끝나는 시간 push)
        else: #모두 상담중일 때 -> 기다리는 시간 계산
            #우선순위큐로 상담이 가장 빨리 끝나는 멘토 꺼내기
            earliest_end = heapq.heappop(queue)
            wait_time = max(0, earliest_end - start)
            total_waiting_time += wait_time
            heapq.heappush(queue, max(earliest_end, start) + duration) #상담이 실제 끝나는 시간
    
    return total_waiting_time
            

def solution(k, n, reqs):
    
    min_wating_time = 10**9 
    
    #(1)가능한 멘토 배정 조합 생성
    for mentor_list in generate_mentor(n,k):
        #(2)상담 대기 시간 계산
        cal_min_wating_time = calculate_wating_time(reqs, mentor_list, k)
        min_wating_time = min(min_wating_time, cal_min_wating_time)
    
    return min_wating_time