<Lv.3> 상담원 인원 (프로그래머스 : C#)

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

📕 문제 설명

참가자가 상담 요청을 하면 아래의 규칙대로 진행됨

1. 상담을 원하는 참가자가 상담 요청시, 참가자의 상담 유형을 담당하는 멘토 중 상담중이 아닌 멘토와 상담 시작
2. 모두 상담중이면 기다림. 참가자가 기다린 시간은 상담 요청~멘토와 상담 시작때까지의 시간
3. 모든 멘토는 상담 끝나고 기다리는 참가자 있으면 즉시 상담 시작 (먼저 요청한 참가자 우선)

참가자의 상담 요청 정보가 주어질 때 참가자가 상담 요청~상담 시작까지 기다린 시간 합이 최소가 되도록 각 상담 유형별로 멘토 인원 정함

멘토 인원 적절히 배정했다고 했을 때 최소 기다린 시간 합 반환하기

• Input
  상담 유형의 수, 멘토의 수, 참가자와 상담 요청
• Output
  멘토 인원을 적절히 배정했을 때 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 값의 최솟값

예제

풀이

상담 유형 별로 1~최대 배정할 수 있는 인원수에 대해 각자 요구되는 최소 대기시간을 구한다. 그 다음 재귀로 각 유형별로 최소 대기 시간을 가질 수 있는 조합을 찾아 반환한다.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(int k, int n, int[,] reqs) {
        int answer = 0;
        
        var timeByType = new List<(int start, int time)>[n+1];
        
        for(int i = 0; i <= n; i++) 
        {
            timeByType[i] = new List<(int, int)>();
        }
        
        for (int i = 0; i < reqs.GetLength(0); i++)
        {
            timeByType[reqs[i, 2]].Add((reqs[i, 0], reqs[i, 1]));
        }

        int[,] sum_wait = new int[k+1, n-k+2];
        
        for(int i = 1; i <= k; i++) 
        {     
            for(int j = 1; j <= n-k+1; j++) 
            {
                PriorityQueue pq = new PriorityQueue();
                foreach(var node in timeByType[i])
                {
                    // 현재 상담 인원 수 < 배정 가능한 상담원 수
                    if(pq.Count < j) // 바로 상담 가능
                    {
                        pq.Enqueue(node.start + node.time);
                    }
                    else 
                    {
                        // 제일 빨리 상담 끝나는애 가져오기
                        int min = pq.Dequeue();
                        int wait = min - node.start; // 기다리는 시간
                        if(wait > 0) 
                        {
                            sum_wait[i, j] += wait;
                            pq.Enqueue(min + node.time);
                        }
                        else 
                        {
                            pq.Enqueue(node.start + node.time); // 기다리는 시간 0이면 시작 + 걸리는 시간
                        }
                    }
                }
            }
        }
        
        answer = DFS(n-k+1, sum_wait, 1, k);
        return answer;
    }
    public int DFS(int remain, int[,] wait, int depth, int k)  // 상담원 조합 찾기
    {
        if(depth > k) return 0;
        int sum = 100000000;
        // 최소 대기 시간 합 구하기 
        for(int i = 1; i <= remain; i++) 
        {
            sum = Math.Min(DFS(remain-i+1, wait, depth+1, k) + wait[depth,i], sum);
        }
        
        return sum;
    }
}

public class PriorityQueue // MinHeap
{
    private List<int> heap = new List<int>();

    public int Count => heap.Count;
    
    public void Enqueue(int data)
    {
        heap.Add(data);
        int now = heap.Count - 1; // 추가한 노드 위치 (트리 마지막 레벨 왼쪽)
        
        while (now > 0) // 순서 지정하기
        {
            int next = (now - 1) / 2; // 부모 노드 (트리)
            if (heap[now] > heap[next]) break;
            int temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;
            now = next;
        }
    }
    
    public int Dequeue()
    {
        int ret = heap[0]; // return할 값 (트리 root에 max 저장해둔 형태)
        int lastIndex = heap.Count - 1;
        heap[0] = heap[lastIndex];
        heap.RemoveAt(lastIndex);
        lastIndex -= 1;
        int now = 0;
        
        while (true)
        {
            int left = 2 * now + 1;
            int right = 2 * now + 2;
            int next = now;
            
            if (left <= lastIndex && heap[next] > heap[left]) next = left;
            if (right <= lastIndex && heap[next] > heap[right]) next = right;
            if (next == now) break;
           
            int temp = heap[now];
            heap[now] = heap[next];
            heap[next] = temp;
            
            now = next;
        }
        
        return ret;
    }
    
    public void Remove(int value)
    {
        heap.Remove(value);
    }
}

결과