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

문제

코딩테스트 연습 - 상담원 인원

알고리즘 문제 연습 카카오톡 친구해요! 프로그래머스 교육 카카오 채널을 만들었어요. 여기를 눌러, 친구 추가를 해주세요. 신규 교육 과정 소식은 물론 다양한 이벤트 소식을 가장 먼저 알려드립니다.

school.programmers.co.kr

문제 정리

요약

• 1 ~ k 번으로 분류된 상담 유형이 존재합니다.
• n 명의 멘토가 존재합니다. 각 멘토는 자신이 담당하는 유형만 상담 가능합니다.
  • 멘토는 한 번에 참가자 한 명만 상담할 수 있습니다.
• 멘토는 다음과 같은 규칙으로 상담을 진행합니다.
  1. 멘토가 상담하지 않을 때 상담 요청이 들어오면 바로 상담을 진행합니다.
  2. 상담 시간은 참가자고 요청한 시간만큼 수행합니다.
  3. 멘토가 상담이 끝나고 상담을 기다리는 참가자가 있으면 바로 상담을 시작합니다.
     • 이때 먼저 상담을 요청한 참가자를 우선으로 상담합니다.
• 참가자 대기 시간은 참가자가 상담을 요청한 순간부터 상담을 시작할 때까지의 시간입니다.
• 참가자 대기 시간이 최소가 되도록 유형별로 상담 멘토 인원을 정하려고 합니다.
  • 단, 유형별로 최소한 한 명의 멘토가 있어야 합니다.

입력 조건

• k (유형 개수) : 1 ~ 5
• n (멘토 인원) : k ~ 20
• reqs (참가자) : 3 ~ 500
  • reqs는 원소가 [a, b, c] 형태로 길이가 3인 정수 배열입니다.
  • a (요청 시간) : 1 ~ 1000
  • b (상담 시간) : 1 ~ 100
  • c (상담 유형) : 1 ~ k

출력

모든 참가자 상담받기까지 기다린 시간의 합의 최솟값을 반환.

---

문제 풀이

Part 1 : 문제 파악

  k와 n의 범위가 작으므로 각 상담 유형에 멘토를 어떻게 배치할지에 대해 모든 경우를 완전 탐색하는 접근이 가능합니다.

각 유형에 최소 1명의 멘토가 필요하므로, 남은 (n - k)명의 멘토를 k개의 유형에 분배하는 문제로 볼 수 있습니다. 이는 중복 조합 문제로 경우의 수는 다음과 같습니다.

\[\binom{(n-k)+k-1}{k-1} = \binom{n-1}{k-1}\]

최악의 경우 n = 20, k = 5로 \({}_{19}\mathrm{C}_{4} = 3876\) 가지 존재합니다.

그리고 경우마다 참가자 수만큼 계산해야 합니다. 이때 참가자는 최대 500명입니다.

따라서 전체 시간 복잡도는 다음과 같습니다.

\[O(3876 \times 500) \approx O(10^6)\]

으로 충분히 제한 시간 내에 수행 가능합니다.

Part 2 : 총 대기 시간 계산

참가자별 대기 시간 계산 방식은 다음과 같습니다.

• 유형 별로 멘토 수만큼 “상담 종료 시간”을 관리합니다.
• 요청이 들어오면 가장 빨리 끝나는 멘토에게 배정합니다.
• 상담 종료 이후에 요청한 경우 - 대기 시간 = 0
• 상담 종료 이전에 요청한 경우 - 대기 시간 = 상담 종료 시간 - 요청 시간

---

풀이 코드

def solution(k, n, reqs):
    
    answer = 10 ** 10
    
    # counselor: 각 유형에 따른 배정된 상담원 수
    for counselor in get_counselors([1] * k, n - k, 0):
        # DB: 각 유형 별 멘토들 상담 종료 시간
        DB = {i: [0] * counselor[i] for i in range(k)}

        # 총 대기 시간
        wait = 0
        
        for req in reqs:
            counsel_type = req[2] - 1
            counsel_state = DB[counsel_type]
            
            best_idx = max(range(counselor[counsel_type]),
                         key=lambda i: req[0] - counsel_state[i])
            
            if req[0] >= counsel_state[best_idx]:
                # 상담 종료 후에 요청 - 대기 시간 0

                DB[counsel_type][best_idx] = req[0] + req[1]

            else:
                # 상담 종료 전에 요청, 종료 후 바로 상담 시작
                wait += counsel_state[best_idx] - req[0]

                DB[counsel_type][best_idx] += req[1]
                
        answer = min(answer, wait)
        
    return answer

# 모든 상담원 배경 경우의 수 구하기.
def get_counselors(arr, n, idx):
    if n == 0:
        yield arr
    else:
        for i in range(idx, len(arr)):
            arr[i] += 1
            yield from get_counselors(arr, n - 1, i)
            arr[i] -= 1

---

회고

구현 과정에서 대기 시간을 계산하는 로직에서 실수를 했습니다.

문제 코드

  counsel_state = DB[counsel_type]

  # ... 중간 생략 ... 

  else:
      # 상담 종료 전에 요청, 종료 후 바로 상담 시작
      DB[counsel_type][best_idx] += req[1]

      wait += counsel_state[best_idx] - req[0]

문제 원인

• counsel_state = DB[counsel_type]는 값 복사가 아니라 참조(reference) 입니다.
• 그 결과 대기 시간을 계산할 때 이미 갱신된 상담 종료 시간을 사용하게 되면서 틀리게 되었습니다.

놓친 부분

• 값 복사인지 참조인지 의식하지 않고 사용했습니다.
• 상태를 갱신(DB 변경)하는 시점과 그 값을 사용하는 시점을 명확하게 구분했습니다.

---

최적화

실행 결과, 최악의 경우 테스트 9 > 통과 (1489.46ms, 9.33MB)로 약 1.5초의 수행 시간이 소요되는 것을 확인하였습니다. 입력 크기에 비하여 너무 긴 시간이 걸린다고 판단하여 시간 복잡도를 개선하기 위한 최적화를 진행하였습니다.

1차 최적화 - min heap 도입

best_idx = max(range(counselor[counsel_type]), 
                key=lambda i: req[0] - counsel_state[i])

  할당받을 멘토를 선택하는 과정에서 모든 멘토의 종료 시간을 검토하여 가장 빨리 배정할 수 있는 멘토를 찾고 있습니다. 이 경우에는 힙을 통하여 O(N) -> O(logN) 으로 시간을 단축할 수 있습니다.

2차 최적화 - DP 도입

  현재 로직은 유형 별 상담원 배치 경우의 수를 모두 탐색하여 대기 시간을 계산하고 있습니다. 예를 들어 3가지 유형에 4명 멘토의 경우 counselor = [2, 1, 1], [1, 2, 1], [1, 1, 2]와 같이 모든 케이스를 각각 계산하게 됩니다.

  이때 유형 별로 보면 특정 유형에 멘토를 x명 배치했을 때의 대기 시간은 여러 케이스에서 중복으로 계산되고 있습니다. 1번 유형에 1명을 배치한 경우를 2번 계산하고 있는 것을 알 수 있습니다.

따라서 DP를 도입하여 각 유형에 1 ~ n - k + 1 명의 멘토를 배정했을 때 필요한 대기 시간을 구하고 재사용을 통하여 연산을 최적화하였습니다.

결과

최악의 테스트 케이스였던 테스트 9의 수행 시간이 1489.46ms -> 27.81ms로 개선되었습니다.

개선된 코드

from heapq import heappush, heappop
from collections import defaultdict

def solution(k, n, reqs):

    answer = 10 ** 10
    
    # 상담 유형 별로 분리
    map_k_reqs = defaultdict(list)
    
    for req in reqs:
        map_k_reqs[req[2] - 1].append([req[0], req[1]])

    
    # DP[k][i] = k 유형 상담에 i 명의 상담사 있을 때 대기 시간 계산
    DP = {_: [0] * (n - k + 2)  for _ in range(k)}
    
    for now_n in range(1, n - k + 2):
        
        for now_k in map_k_reqs:
            counselors = [0] * now_n
            wait_time = 0
            
            for req in map_k_reqs[now_k]:
                last_time = heappop(counselors)
                
                if req[0] >= last_time:
                    heappush(counselors, req[0] + req[1])
                else:
                    wait_time += last_time - req[0]
                    heappush(counselors, last_time + req[1])
            
            DP[now_k][now_n] = wait_time
                
    # 각 멘토 배치 경우 수에 따른 대기 시간 계산
    for counselors in get_counselors([1] * k, n - k, 0):
        
        wait = sum(DP[k_][c_] for k_, c_ in enumerate(counselors))
        
        answer = min(answer, wait)
        
    
    return answer

def get_counselors(arr, n, idx):
    if n == 0:
        yield arr
    else:
        for i in range(idx, len(arr)):
            arr[i] += 1
            yield from get_counselors(arr, n - 1, i)
            arr[i] -= 1

---

Greedy 풀이 (다른 풀이 참고)

문제 풀고, 다른 사람의 풀이에서 lurin0712 님의 코드를 해석하면서 알게되었습니다.

아이디어

이 문제는 그리디로 해결할 수 있습니다. i 유형의 참여자를 프로세스로 보고 멘토를 프로세서라고 생각하면 결국 병렬 처리에서 한계 효용에 의하여 “멘토 수 증가에 따라 대기 시간 감소량이 단조 감소”합니다.

각 상담 유형 i에 대해, 멘토 수를 늘릴 때의 대기 시간을 다음과 같이 정의합니다.

• di,1 : 멘토 1명에서 2명으로 증가 시 감소량
• di,2 : 멘토 2명에서 3명으로 증가 시 감소량
• …

이때 항상 다음이 성립합니다.

\[d_{i,1} \ge d_{i,2} \ge d_{i,3} \ge \cdots\]

이제 남은 멘토를 한 명씩 배치한다고 생각해 보면, 각 유형에 “멘토를 1명 추가했을 때 대기 시간 감소량이 가장 큰 상담 유형”을 선택하는 것이 항상 최적이 됩니다.

풀이 코드

from heapq import heappush, heappop
from collections import defaultdict


def solution(k, n, reqs):
    
    answer = 0
    
    # 상담 유형 별로 분리
    map_k_reqs = defaultdict(list)
    
    for req in reqs:
        map_k_reqs[req[2] - 1].append([req[0], req[1]])

    # 멘토를 추가할 때 감소되는 대기 시간을 나타냄.
    # diff_heap[i] = [a, b, c, d]
    #   - a : 감소되는 대기 시간량
    #   - b : 상담 요청 타입,
    #   - c : 멘토 인원 수
    #   - d : 대기 시간.
    diff_heap = []
    
    for now_k in map_k_reqs:
        # 멘토 1명인 경우
        wait_time1 = get_wait_time(1, map_k_reqs[now_k])
        
        # 멘토 2명인 경우
        wait_time2 = get_wait_time(2, map_k_reqs[now_k])
        
        answer += wait_time1 # 1명은 기본으로 포함되므로 총 대기 시간에 더하기
        
        diff = [wait_time2 - wait_time1, now_k, 2, wait_time2]
        
        heappush(diff_heap, diff)
    
    # 남은 멘토들을 그리디로 하나씩 결정하기
    for i in range(n - k):
        # 항상 가장 많은 대기 시간 감소를 가지는 것을 선택
        now = heappop(diff_heap) 
        
        # 감소량 만큼 대기 시간 감소 시키기
        answer += now[0] 
        
        # 새로운 선택지 추가하기
        wait_time = get_wait_time(now[2] + 1, map_k_reqs[now[1]])
        
        next_diff = [wait_time - now[3], now[1], now[2] + 1, wait_time]
        
        heappush(diff_heap, next_diff)
        
    return answer


def get_wait_time(mentor_cnt, reqs):
    mentors = [0] * mentor_cnt
    wait_time = 0
    
    for req in reqs:
        last_time = heappop(mentors)
        
        if req[0] >= last_time:
            heappush(mentors, req[0] + req[1])
        else:
            wait_time += last_time - req[0]
            heappush(mentors, last_time + req[1])
    
    return wait_time

결과

최악의 테스트 케이스였던 테스트 9의 수행 시간이 27.81 -> 3.06ms로 개선되었습니다.

---

참고 문헌

• https://en.wikipedia.org/wiki/Amdahl%27s_law