Programmers / 상담원 인원 / Python

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 상담원 인원 (3단계)

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스

 

문제 설명

---

나의 풀이

def solution(k, n, reqs):
    import heapq

    # 1. 유형별 요청 정리
    counsel = {i: [] for i in range(1, k + 1)}
    
    for start, ing, t in reqs:
        counsel[t].append((start, ing))

    # 2. 대기시간 계산 함수
    def wait_time_for_type(requests, mentor_count):
        waiting_time = 0
        end_times = []
        for start, duration in requests:
            if len(end_times) < mentor_count:
                heapq.heappush(end_times, start + duration)
            else:
                earliest_end = heapq.heappop(end_times)
                if earliest_end <= start:
                    heapq.heappush(end_times, start + duration)
                else:
                    waiting_time += earliest_end - start
                    heapq.heappush(end_times, earliest_end + duration)
        return waiting_time

    # 3. 멘토 분배 조합
    def distribute_mentors(n, k):
        result = []
        def dfs(i, remain, current):
            if i == k:
                if remain == 0:
                    result.append(current[:])
                return
            for x in range(1, remain - (k - i - 1) + 1):
                current.append(x)
                dfs(i + 1, remain - x, current)
                current.pop()
        dfs(0, n, [])
        return result

    # 4. 모든 분배 조합에 대해 최소 대기시간 계산
    min_wait = float('inf')
    for case in distribute_mentors(n, k):
        total_wait = 0
        for t in range(1, k + 1):
            total_wait += wait_time_for_type(counsel[t], case[t - 1])
        min_wait = min(min_wait, total_wait)
        
    return min_wait

---

※ 알아야 할 것

힙을 사용하는 이유는 멘토가 여러 명일 때, 항상 '가장 빨리 끝나는 멘토”를 찾아야 하는데 그걸 매번 min()으로 찾으면 O(N)이라 느립니다.

힙을 쓰면

• 삽입: O(log N)
• 꺼내기: O(log N)
  로 빠르게 관리할 수 있습니다.

즉, 효율적인 시뮬레이션이 가능해집니다.