[Python] 상담원 인원

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

프로그래머스

---

[풀이 코드]

from collections import Counter, defaultdict
from itertools import combinations_with_replacement
def solution(k, n, reqs):
    # 큰 수
    answer = 999999999
    # 중복조합
    comb = combinations_with_replacement([i for i in range(k)], r=n-k)
    # 상담원-유형 케이스목록 구하기
    cases = []
    for case in comb:
        base = [1 for i in range(k)]
        for c in case:
            base[c] += 1
        cases.append(base)
    # 참가자 데이터 가공 문제유형 : [시작시간, 종료시간]
    participants = defaultdict(list)
    for start_time, minutes, category in reqs:
        participants[category].append([start_time, start_time + minutes])
    # 각 케이스에 대해 wait_time을 구하고 최소값 찾기
    for case in cases:
        wait_time = 0 
        # 각 유형에 대해  wait_time 계산하여 더하기
        for i in range(k):
            p_list = sorted(participants[i+1], key=lambda x:x[0])
            mento_list = [0 for _ in range(case[i])]
            for start_time, end_time in p_list:
                mento_list = sorted(mento_list)
                if mento_list[0] <= start_time:
                    mento_list[0] = end_time
                else:
                    temp_t = mento_list[0] - start_time
                    mento_list[0] = end_time + temp_t
                    wait_time += temp_t
            #수행 중 만약 현재 최소값보다 길어지면 break
            if wait_time > answer:
                break
        if wait_time < answer:
            answer = wait_time
    return answer

 

[풀이]

1. n명의 상담원에 대해 k개의 상담 유형이 매치되어야한다. (n >= k)

- combinations_with_replacement(중복 조합) 사용한다.

- 이때 상담유형에 대해 최소 한 명의 상담원은 존재하여야 한다. 따라서  n-k개 선택에 대한 조합을 구하고,

base(1로 초기화 된 길이가 k인 리스트) 에 해당 조합을 더하여 매치되는 모든 케이스를 구한다.

 

2. 참가자 데이터 가공

- 상담유형을 키 값으로 하고 값으로 [시작시간, 종료시간]을 가지는 딕셔너리를 사용한다.

- 위 형식으로 데이터를 가공한다.

 

3.1. wait_time 구하기

- 각각의 case에 대해 wait_time을 구해서 최소값을 찾는다.

- 각 유형은 독립적이므로, 각 유형에 대한 wait_time의 합이 각각의 case의 wait_time이다.

 

3.2. 유형에 대한 wait_time을 구하기 위해, 각 멘토의 상담종료시간을 저장하고 있을 mento_list 사용

- 예를들어 참가자가 1번 멘토에 대해 상담을 시작하려할때, mento_list[0]의 값이 참가자의 시작시간보다 이후이면

참가자는 기다려야한다.

- mento_list의 경우 정렬을 통해 항상 맨 앞(0번 인덱스)에 가장 작은 값(가장 빠른 시간)이 위치하게 한다.

 

3-3. 참가자가 (기다려야 하는/기다리지 않아도) 되는 경우

- 만약 참가자가 기다리지 않아도 되는경우 mento_list[0]을 상담 종료 시간으로 변경한다.

- 만약 참가자가 기다려야 하는 경우 wait_time에 기다려야 하는 시간을 더하고, mento_list[0]를 (상담 종료 시간 + 기다려야 하는 시간)으로 변경한다.