프로그래머스 상담원 인원 (JAVA)

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

프로그래머스

 

저는 우선순위 큐를 통해 문제를 해결하였습니다. 

먼저 각각의 k개에 인원을 배치 후, 각 type에 맞게 우선순위 큐에 넣었습니다. 이 사이즈가 각 배치한 인원들 보다 크다면 우선순위 큐에서 한명 빼고 다음 사람을 넣어줍니다. 이때 넣어질 사람의 시작 시간보다 나올 사람의 끝나는 시간이 더 빠르다면, 그 차이만큼 결과값에 더해줍니다. 

 

import java.util.*;
class Solution {
    public int solution(int k, int n, int[][] reqs) {
        int[] people = new int[k];
        int answer = cal(0,n,k,people,reqs);
        return answer;
    }
    private static final int INF = 987654321;
    private static int cal(int depth, int n, int k,int[] people, int[][] reqs){
        if(depth == k && n == 0){
            return calWaitTime(people,k,reqs);
        }
        if(depth == k){
            return INF;
        }
        int result = INF;
        for(int i = 1 ; i <= n ; i++){
            people[depth] = i;
            result = Math.min(result,cal(depth+1,n-i,k,people,reqs));
        }
        return result;
    }
    private static int calWaitTime(int[] people, int k, int[][] reqs){
        int waitTime = 0;
        PriorityQueue<Integer>[] q = new PriorityQueue[k];
        for(int i = 0 ; i < k ; i++){
            q[i] = new PriorityQueue<>();
        }
        for(int[] req : reqs){
            int startTime = req[0];
            int duringTime = req[1];
            int type = req[2] - 1;
            int time = startTime;
            if(q[type].size() >= people[type]){
                int endTime = q[type].poll();
                if(endTime > startTime){
                    waitTime += endTime - startTime;
                    time = endTime;
                }
            }
            q[type].add(time + duringTime);
        }
        return waitTime;
    }
}