[programmers] Lv3 상담원 인원 - Python

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

프로그래머스

 

 

 

<문제 풀이>

-  질문하기의 힌트를 참고해 해결했다. 이를 통해 itertools의 중복 조합 뽑기를 알게 되었으며, 멘토가 유형별로 배치되는 경우의 수를 쉽게 구할 수 있다. combinations(iterable, r)이 원소의 수가 r개인 조합을 생성하는 것이라면 combinations_with_replacement(iterable, r)는 원소의 수가 r개인 중복 조합 뽑기 이다.

- heapq의 최소힙을 이용해 상담 시간이 빠르게 끝나는 멘토와 대기자의 상담 시간을 비교하여 대기 시간을 구했다.

- 이때 heap의 원소의 수 = 멘토의 수를 이용했다.

 

 

 

<Code>

import heapq
from itertools import combinations_with_replacement, permutations


def solution(k, n, reqs):
    answer = float('inf')    # 초기값

    schedule = [[] for _ in range(k)]    # 상담 유형별로 상담요청 분류
    for req in reqs:
        schedule[req[2]-1].append([req[0], req[1]])

    cases = set()    # 유형별로 멘토들을 배치 했을 때 나오는 경우의 수
    arr = [i for i in range(1, n - k + 2)]    # 각 유형에 나올 수 있는 멘토의 수
    for com in combinations_with_replacement(arr, k):    # 중복조합으로 경우의 수 생성
        if com not in cases and sum(com) == n:    # 이미 나온 경우의 수가 아니며 멘토의 수가 맞는지 확인
            for per in permutations(com, k):    # 해당 인원들로 각 유형에 적용해 나올 수 있는 모든 경우 추가
                cases.add(per)

    for case in cases:    # 유형별로 배치된 멘토들의 경우의 수를 체크
        total = 0    # 총 대기 시간

        for i in range(k):
            heap = [0] * case[i]    # 힙 생성

            for st, du in schedule[i]:
                prev = heapq.heappop(heap)
                if st >= prev:    # 시작시간이 이전 종료 시간 이후라면 대기 시간없이 진행
                    heapq.heappush(heap, st + du)
                else:    # 그게 아닌 경우 대기 시간 추가 후 상담 진행
                    total += prev - st
                    heapq.heappush(heap, prev + du)

        answer = min(answer, total)    # 최소 대기 시간으로 변경

    return answer

※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.