상담원 인원

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/214288

---

풀이

N ≤ 20이라 재귀+브루트포스로 풀었다.

• K개의 유형에 상담원을 분배한다.
• 상담원 분배가 끝나면, 총 대기시간을 계산한다.
• 모든 경우의 수에 대해 (1)~(2)를 반복하고, 최소 대기시간을 찾는다.

(1) 상담원 분배하기

// static int answer = Integer.MAX_VALUE
// static int N;
	public void pick(int category, int sum, int[][] reqs) {
        if(category==K) {
            if(sum!=N) return; // 총 상담원의 수가 N명보다 적으면 return
            // N명의 상담원을 K개의 유형에 모두 배정했으면 대기시간 계산
            answer = Math.min(answer, calculateWatingTime(reqs));
            return;
        }
        
        for (int i=1; i<=N-sum; i++) {
            counselor[category] = i;
            pick(category+1, sum+i, reqs);
        }
    }

• category: 몇번 유형에 상담원을 분배할 것인지
• sum: 현재까지 분배한 상담원의 수
• counselor[n]: n+1번 유형에 분배한 상담원의 수

재귀를 이용해 상담원을 분배해준다. 현재 유형에 분배할 수 있는 상담원의 수는 1명 ~ (전체 상담원의 수- 현재까지 분배한 상담원의 수) 이므로, 1부터 N-sum까지 모든 경우의 수를 탐색해준다.

종료 조건은 (1) 모든 유형에 상담원을 분배했고, (2) 분배한 상담원의 수가 총 N명일 때이다. 종료 조건을 충족하면 총 대기시간을 계산하고, 최소값을 갱신한다.

(2) 총 대기시간 계산

    public int calculateWatingTime(int[][] reqs) {
    	// 총 대기시간
        int result = 0;
        
        // q[i]: 진행중인 (i-1)번 유형 상담의 종료시간을 저장하는 큐
        // PriorityQueue이므로 가장 빨리 끝나는 상담의 종료시간을 반환함
        PriorityQueue<Integer>[] q = new PriorityQueue[K];
        for (int i=0; i<K; i++) {
            q[i] = new PriorityQueue<>();
        }
        
        for (int i=0; i<reqs.length; i++) {
            int startTime = reqs[i][0];
            int time = reqs[i][1];
            int idx = reqs[i][2]-1;
            
            // 상담을 배정받지 않은 상담사가 있으면, 상담을 배정해줌
            // 끝나는 시각 = 시작 시각 + 상담 진행시간
            if(q[idx].size()<counselor[idx]) {
                q[idx].add(startTime+time);
                continue;
            }
            
            // 만약 모든 상담사가 상담중이면, 가장 빠르게 예약 가능한 시간을 찾음
            int prevEndTime = q[idx].poll();
            // 가장 빠른 예약가능시간이 예약 희망시간보다 뒤인 경우 -> 대기
            if(prevEndTime>startTime) {
                result+=(prevEndTime-startTime);
                q[idx].add(prevEndTime+time);
            // 이전 상담이 예약 희망시간보다 먼저 종료되는 경우 -> 상담 정상진행
            } else {
                q[idx].add(startTime+time);
            }
        }
        return result;
    }

상담을 진행하는 경우는 3가지 경우가 있다.

• 상담을 배정받지 않은 상담사가 있는 경우 → 예약 시간에 상담 진행
• 모든 상담사가 상담을 배정받은 경우: 가장 빠르게 예약 가능한 시간을 찾아야 함
  • 가장 빠른 예약 가능 시간 ≤ 예약 희망 시간 → 예약 시간에 상담 진행
  • 가장 빠른 예약 가능 시간 > 예약 희망 시간→ 대기 발생!

먼저 우선순위 큐를 K개 생성한다. 큐에는 상담 종료 시간이 들어가는데, 우선순위 큐로 선언했기 때문에 가장 빠른 종료 시간을 반환하게 된다.

그 후, reqs 배열을 훑으며 원하는 시작 시간 startTime, 진행 시간 time, 상담 유형 idx를 받아온다. 만약 q[idx]의 사이즈가 해당 유형에 배정한 상담사 수보다 작으면, 상담을 배정받지 않은 상담사가 있다는 의미이다. 따라서 현재 상담의 종료 예정 시간을 큐에 추가한다.

q[idx]의 사이즈가 상담사 수와 같거나 크면, 모든 상담사가 상담을 1개 이상 배정받은 상태이다. 이 상태에서는 가장 빠른 예약 가능 시간을 확인해야 한다.
큐에서 원소를 빼내 가장 빠른 상담 종료시간 prevEndTime을 예약 희망 시간 startTime과 비교한다.

• prevEndTime > startTime: 웨이팅이 발생하므로 대기시간을 result에 더해준다. 현재 상담이 prevEndTime에 시작되므로 종료 예정 시간은 prevEndTime+time이 된다.
• prevEndTime ≤ startTime: 웨이팅이 발생하지 않으므로, 현재 상담은 예정대로 진행된다. 현재 상담의 종료 예정 시간은 startTime+time이 된다.

---

전체 코드

import java.util.*;

class Solution {
    static int[] counselor;
    static int K, N;
    static int answer = Integer.MAX_VALUE;
    public int solution(int k, int n, int[][] reqs) {
        K = k;
        N = n;
        counselor = new int[k];
        
        pick(0,0,reqs);
        return answer;
    }
    
    public void pick(int category, int sum, int[][] reqs) {
        if(category==K) {
            if(sum!=N) return;
            answer = Math.min(answer, calculateWatingTime(reqs));
            return;
        }
        for (int i=1; i<=N-sum; i++) {
            counselor[category] = i;
            pick(category+1, sum+i, reqs);
        }
    }
    
    public int calculateWatingTime(int[][] reqs) {
        int result = 0;
        PriorityQueue<Integer>[] q = new PriorityQueue[K];
        for (int i=0; i<K; i++) {
            q[i] = new PriorityQueue<>();
        }
        
        for (int i=0; i<reqs.length; i++) {
            int startTime = reqs[i][0];
            int time = reqs[i][1];
            int idx = reqs[i][2]-1;
            
            if(q[idx].size()<counselor[idx]) {
                q[idx].add(startTime+time);
                continue;
            }
            
            int prevEndTime = q[idx].poll();
            if(prevEndTime>startTime) {
                result+=(prevEndTime-startTime);
                q[idx].add(prevEndTime+time);
            } else {
                q[idx].add(startTime+time);
            }
        }
        return result;
    }
}