[Programmers] 상담원 인원

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스

문제 풀이

k : 유형의 수, n : 멘토 총인원, req[][] : {시작시간, 진행시간, 유형} 이 매개변수로 주어진다.

시작시간은 중복되지 않으며 오름차순으로 정렬되어 있다.

멘토 인원을 적절히 배정했을 때 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 값의 최솟값을 return해야한다.

각 유형별로 최소 1명씩은 멘토가 있으므로 유형별로 1명일 경우 기다리는 시간을 계산하고 1명을 추가했을 때 기다리는 시간이 가장 많이 줄어드는 유형에 1명을 추가하는 작업을 n명까지 반복한다.
기다리는 시간(waitingTimeArr)의 총합을 출력한다.

 

예제 1번을 예시로 들면

유형 1 : {10, 60, 1}, {20, 30, 1}, {50, 40, 1}, {65, 30, 1}

유형 2 : {60, 30, 2}, {70, 100, 2}

유형 3 : {15, 100, 3}, {30, 50, 3}

각각 멘토 1명씩 배치했을 경우 기다리는 총합은

유형 1 : 175(1), 유형 2 : 20(1), 유형 3 : 85(1)

만약 유형 1부터 1명씩 추가한다고 가정하면 

유형 1 : 5(2), 유형 2 : 0(2), 유형 3: 0(2) 

으로 유형 1이 170차이로 가장 높기 때문에 유형 1의 멘토를 1명 늘릴 수 있다.

유형 1 : 5(2), 유형 2 : 20(1), 유형 3: 85(1) 

멘토의 수(n)이 5명 이므로 1번더 반복하면 유형 3이 85차이로 가장 높기 때문에 멘토 1명을 추가해준다.

결과적으로 유형 1 : 5(2), 유형 2 : 20(1), 유형 3 : 0(2)로 20+5+0=25를 return한다.

코드

import java.util.*;

class Solution {
    public int solution(int k, int n, int[][] reqs) {
        // k:유형의 수, n:멘토의 수
        // init
        List<int[]>[] reqListArr = new ArrayList[k+1];
        int[] mentorNumberArr = new int[k+1];
        int[] waitingTimeArr = new int[k+1];
        
        for(int i=1; i<=k; i++) {
            reqListArr[i] = new ArrayList<>();
            mentorNumberArr[i]++;
        }
        
        // List에 유형별로 시간 저장
        for(int[] req : reqs) {
            reqListArr[req[2]].add(new int[] {req[0], req[1]});
        }
        
        // 유형별로 1명일 때 waitingTime 저장
        for(int i=1; i<=k; i++) {
            waitingTimeArr[i] = getWaitingTime(reqListArr[i], mentorNumberArr[i]);
        }
        
        // cal
        for(int i=k; i<n; i++) {
            int maxTime = 0;
            int maxIndex = 0;
            
            // 기다리는 시간 차이가 가장 큰 maxTime, maxIndex 구하기
            for(int j=1; j<=k; j++) {
                int waitingTime = getWaitingTime(reqListArr[j], mentorNumberArr[j] + 1);
                if(maxTime < waitingTimeArr[j] - waitingTime) {
                    maxTime = waitingTimeArr[j] - waitingTime;
                    maxIndex = j;
                }
            }
            
            // max값에 의해 인원 수와 기다리는 시간 저장
            waitingTimeArr[maxIndex] -= maxTime;
            mentorNumberArr[maxIndex]++;
        }
        
        int answer = 0;
        for(int time : waitingTimeArr) {
            answer += time;
        }
    
        return answer;        
    }    
    
    // 인원 수에 맞춘 기다리는 시간 계산
    public int getWaitingTime(List<int[]> reqList, int peopleNumber) {
        // 끝나는 시간 우선순위 큐
        PriorityQueue<Integer> timeQueue = new PriorityQueue<>();        
        int waitingTime = 0;
        
        for(int[] req : reqList) {
            if(timeQueue.size() >= peopleNumber) {
                int time = timeQueue.poll();
                if(req[0] < time) {
                    waitingTime += (time - req[0]);
                    timeQueue.add(time + req[1]);
                    continue;
                } 
            }
            timeQueue.add(req[0] + req[1]);
        }
        
        return waitingTime;
    }
}