[프로그래머스/Lv3] 상담원 인원 (Python)

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

프로그래머스

 

Status : Solved

 

Time : 00:35:19

 

---

 

문제 설명

 

 

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

참가자가 상담 요청을 하면 아래와 같은 규칙대로 상담을 진행합니다.

 

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

 

* 예시 설명은 위 링크를 참조해 주세요

 

상담 유형의 수를 나타내는 정수 k, 멘토의 수를 나타내는 정수 n과 참가자의 상담 요청을 담은 2차원 정수 배열 reqs가 매개변수로 주어집니다. 멘토 인원을 적절히 배정했을 때 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 값의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

 

 

입력 및 출력

 

제한사항

 

• 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	answer
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

 

 

---

 

풀이

 

간만에 나온 프로그래머스 문제! 반가운 마음에 하나씩 집어들었다. 프로그래머스 환경에 다시금 적응하는 데 시간이 필요할 듯 싶다. 아니면 내 머리 회전이 느려졌거나..

 

언뜻 보면 복잡해 보이나, k, n의 크기가 매우 작다는 사실을 눈여겨보자. 상담하는 멘토의 순서는 상관이 없되, 멘토의 배치 명수가 중요하다. 따라서 충분히 모든 조합을 테스트해볼 수 있다.

 

모든 req 타입에 최소한 1명의 상담원이 필요하므로, 실제로는 n-k명의 사람을 배분하는 경우의 수와 동일하다. 따라서 이러한 배분을 먼저 진행하고, 각 배분에 따라 상담 시뮬레이션을 돌려 볼 수 있겠다. 각 시뮬레이션에서 상담은 그리디하게(즉 자리가 비면 무조건 그 상담원에게 먼저 가고, 그렇지 않으면 최소 대기 시간 상담원을 이용하므로) 진행되므로 이 역시 구현하면 끝.

 

문제의 제약 조건이 매우 많아보이게(즉 어려워보이게) 만들어졌다. 기업 출제 문제가 점점 국어 문제를 다루게 되는 경향이 보인다.

 

 

풀이 코드

from collections import defaultdict
MAX = float('inf')

def calculate(n, req_list) :
    result = 0
    mento_list = [0]*(n+1)
    for a, b in req_list :
        best_mento, best_time = -1, MAX
        for i in range(n+1) :
            if best_time > mento_list[i] :
                best_mento, best_time = i, mento_list[i]
        result += max(0, best_time - a)
        mento_list[best_mento] = max(a, best_time) + b
    return result

def combs(left, idx):
    global req_dict, type_list, type_num
    if idx == type_num or not left :
        result = 0
        for i in range(type_num) :
            result += calculate(type_list[i], req_dict[i])
        return result
    
    result = MAX
    for i in range(left+1) :
        type_list[idx] = i
        result = min(result, combs(left-i, idx+1))
    type_list[idx] = 0
    return result

def solution(k, n, reqs):
    global req_dict, type_list, type_num
    type_num = k
    n -= k
    req_dict = defaultdict(list)
    type_list = [0]*k
    for a, b, c in reqs :
        req_dict[c-1].append((a, b))
    
    return combs(n, 0)