[프로그래머스] 상담원 인원

문제

---

• 상담원 인원 (LV3)

상담원 인원

참가자들의 상담 요청 시각, 상담 시간, 상담 유형이 주어졌을 때, n명의 멘토를 적절하게 k개의 상담 유형으로 분류해 참가자들의 대기 시간을 최소로 하는 문제였다.

내 코드

---

dp를 잘 활용하면 문제를 해결할 수 있을 것 같아 비슷한 방식으로 접근해 보았다.
우선 조합을 활용해서 멘토를 각 유형에 분류하는 distribute 메서드를 만들었다.
그 다음 각 멘토들의 조합을 돌면서 대기 시간이 최소가 되는 경우를 탐색하였다.
이때 각 멘토별로 상담시간 리스트를 만들어서 가장 빨리 상담이 가능한 멘토를 찾아서 참가자를 배정하였다.
문제를 풀다보니 dp보다는 그리디에 가까운 코드가 되었다.

from itertools import combinations_with_replacement

def distribute(k, n):
    # 각 상담 유형에 적어도 하나의 멘토가 배정되도록 조합 생성
    remaining_slots = n - k
    distributions = []
    for combo in combinations_with_replacement(range(k), remaining_slots):
        allocation = [1] * k
        for c in combo:
            allocation[c] += 1
        distributions.append(tuple(allocation))
    return distributions

def solution(k, n, reqs):
    mentors = distribute(k, n)
    answer = 10**9

    for mentor in mentors:
        # 상담 유형별 멘토 상태 초기화
        m = {i: [0] * mentor[i - 1] for i in range(1, k + 1)}
        total_wait_time = 0

        for req in reqs:
            start_time, duration, req_type = req

            # 가장 빨리 상담 가능한 멘토 찾기
            min_wait_mentor = m[req_type][0]
            min_wait_index = 0
            for i in range(1, len(m[req_type])):
                if max(m[req_type][i], start_time) < max(min_wait_mentor, start_time):
                    min_wait_mentor = m[req_type][i]
                    min_wait_index = i

            # 대기 시간이 발생하는 경우 계산
            wait_time = max(0, min_wait_mentor - start_time)
            total_wait_time += wait_time
            # 멘토의 사용 종료 시간 업데이트
            m[req_type][min_wait_index] = max(start_time, min_wait_mentor) + duration

        answer = min(answer, total_wait_time)

    return answer

아무래도 코드에 3중 for문을 사용하여서 문제의 입력에 따라서 2초정도까지 시간이 소요되는 것을 볼 수 있었다.
더 나은 시간 복잡도를 가진 코드가 있을지 고민해 봐야겠다.