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

목차

1. 문제
2. 문제 조건
3. 문제 조건 분석
4. 알고리즘
5. 코드

1. 문제

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

2. 문제 조건

멘토 n명 존재, 1~k번으로 분류되는 총 k개의 상담 존재.

• 각 멘토는 k개의 상담 유형 중 하나만 담당 가능
• 멘토는 자신이 담당하는 유형의 상담만 가능
• 멘토는 동시에 한명의 참가자와만 상담 가능
• 상담을 원하는 참가자가 상담 요청 시, 참가자의 상담 유형을 담당하는 멘토 중 현재 상담 중이 아닌 멘토와 상담 시작
• 참가자의 상담 유형 멘토들이 모두 상담 중이면 기다린다.
• 모든 멘토는 상담이 끝났을 때, 기다리는 참가자가 있으면 즉시 상담 시작.

각 유형별로 멘토 인원이 적어도 한 명 이상
👉 현재 주어진 상담 요청에서, 모든 참가자가 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원을 정해야 한다. 이때의 전체 기다린 시간의 합의 최솟값을 반환해라.

1<=k<=5
k<=n<=20
2<=reqs<=300

3. 문제 조건 분석

이 문제를 보고나서, 그리디로 구현할 수 없다는 것을 알고 멘토를 분배하는 것을 백트래킹으로 구현해야 한다.

현재 최대 멘토의 수가 5명, k의 최대가 5개이므로 각 타입의 멘토를 분배하는 것을 백트래킹으로 수행할 수 있다.

4. 알고리즘

멘토를 백트래킹으로 분배하고, 모든 멘토가 분배되었을 때, 기다린 총 합을 계산하면 된다.

기다린 총 합은 pq를 이용해서 간단하게 구할 수 있다.

5. 코드

import java.util.*;

class Solution {
	static int N;
	static int K;
	static List<int[]>[] talks;
	static int[] mentors;

	public int solution(int k, int n, int[][] reqs) {
		N = n;
		K = k;
		talks = new List[k + 1];
		mentors = new int[k + 1];

		Arrays.fill(mentors, 1);

		for (int i = 1; i <= k; i++) {
			talks[i] = new ArrayList<>();
		}

		for (int[] req : reqs) {
			int start = req[0];
			int time = req[1];
			int type = req[2];

			talks[type].add(new int[] { start, time });
		}

		return backTracking(0, 0);
	}

	private int backTracking(int nowN, int idx) {
		if (nowN == N - K) {
			return calMin();
		}

		if (idx == K + 1) {
			return Integer.MAX_VALUE;
		}

		int min = Integer.MAX_VALUE;
		for (int i = 0; i <= N - K - nowN; i++) {
			mentors[idx] += i;
			min = Math.min(min, backTracking(nowN + i, idx + 1));
			mentors[idx] -= i;
		}

		return min;
	}

	private int calMin() {
		int sum = 0;

		for (int i = 1; i <= K; i++) {
			Queue<int[]> queue = new ArrayDeque<>(talks[i]);
			PriorityQueue<Integer> counseling = new PriorityQueue<>();
			int remained = mentors[i]; // 배정된 상담원 인원

			while (!queue.isEmpty()) {
				int[] stu = queue.poll();

				if (remained > 0) {
					counseling.add(stu[1] + stu[0]);// 끝나는 시간 넣어주기
					remained--;

					continue;
				} else {
					// 기다려야 하는 경우
					int latest = counseling.peek();
					if (latest > stu[0]) {
						sum += latest - stu[0];// 기다려야 하는 시간
						counseling.add(latest + stu[1]);
					} else {
						counseling.add(stu[1] + stu[0]);
					}
					counseling.poll();
				}
			}
		}

		return sum;
	}
}