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

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

접근

문제에서 요구하는 바는 멘토를 적절히 배정했을 때 참가자들이 기다린 시간의 합의 최솟값이다.

따라서 이 문제는 멘토를 적절히 배정하는 문제와 참가자들이 기다린 시간의 합의 최소를 구하는 문제로 나눌 수 있다.

우선 멘토를 적절히 배정하는 문제는 제한사항에 따라 멘토를 배정하는 모든 경우의 수를 구하면 된다고 생각했다.

멘토가 각 유형별로 아무리 많아봤자 $n-k=15$ 이기 때문에 문제를 해결하는 데 시간은 충분하다.

다음으로 참가자들이 기다린 시간의 합의 최소를 구해야 한다.

최적화를 고려하면 분마다 iteration 하는 것보다는 reqs 을 그대로 iteration하여 각 차이를 계산하여 결과를 산출하는 게 더 효율적이다.

그리고 reqs 에 있는 원소들은 상담 종료 시각의 순서가 고려되어 있지 않기 때문에 우선순위 큐를 활용하여 상담 종료 시각이 작은 순으로 저장하여 모든 차이를 계산한다.

마지막으로 재귀함수를 활용해 배정되는 모든 멘토 조합에 대해 참가자들이 기다린 시간의 합의 최솟값을 구한다.

소스코드(Java)

import java.util.*;

class Solution {

    int recursive(int maxMentorCount, int[][] gaps, int type) {
        int min = 5 * 1100 * 1100;
        for(int i = 0; i <= maxMentorCount; i++) {
            int sum = gaps[type][i];
            if(type < gaps.length - 1) {
                sum += recursive(maxMentorCount-i, gaps, type+1);
            }
            min = Math.min(min, sum);
        }
        return min;
    }

    public int solution(int k, int n, int[][] reqs) {

        List<List<Integer[]>> times = new ArrayList<>();
        for(int i = 0; i <= k; i++) {
            times.add(new ArrayList<>());
        }
        for(int[] req : reqs) {
            int start = req[0];
            int end = req[0] + req[1];
            int type = req[2];
            times.get(type).add(new Integer[] { start, end });
        }
        int[][] gaps = new int[k+1][n-k+1];
        for(int i = 1; i <= k; i++) {
            for(int j = 0; j < gaps[i].length; j++) {
                PriorityQueue<Integer> pq = new PriorityQueue<>();
                int maxMentorCount = j + 1;
                int menteeCount = 0;
                int total = 0;
                for(Integer[] time : times.get(i)) {
                    int start = time[0];
                    int end = time[1];
                    while(!pq.isEmpty() && start >= pq.peek()) {
                        pq.poll();
                        menteeCount -= 1;
                    }
                    if(pq.isEmpty() || start < pq.peek()) {
                        menteeCount += 1;
                    }
                    if(menteeCount > maxMentorCount) {
                        int gap = pq.poll() - start;
                        end += gap;
                        total += gap;
                        menteeCount -= 1;
                    }
                    pq.add(end);
                }
                gaps[i][j] = total;
            }
        }
        return recursive(n-k, gaps, 1);
    }
}