문제
현대모비스는 우수한 SW 인재 채용을 위해 상시로 채용 설명회를 진행하고 있습니다. 채용 설명회에서는 채용과 관련된 상담을 원하는 참가자에게 멘토와 1:1로 상담할 수 있는 기회를 제공합니다. 채용 설명회에는 멘토 n명이 있으며, 1~k번으로 분류되는 상담 유형이 있습니다. 각 멘토는 k개의 상담 유형 중 하나만 담당할 수 있습니다. 멘토는 자신이 담당하는 유형의 상담만 가능하며, 다른 유형의 상담은 불가능합니다. 멘토는 동시에 참가자 한 명과만 상담 가능하며, 상담 시간은 정확히 참가자가 요청한 시간만큼 걸립니다.
참가자가 상담 요청을 하면 아래와 같은 규칙대로 상담을 진행합니다.
상담을 원하는 참가자가 상담 요청을 했을 때, 참가자의 상담 유형을 담당하는 멘토 중 상담 중이 아닌 멘토와 상담을 시작합니다.
만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다립니다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간입니다.
모든 멘토는 상담이 끝났을 때 자신의 상담 유형의 상담을 받기 위해 기다리고 있는 참가자가 있으면 즉시 상담을 시작합니다. 이때, 먼저 상담 요청한 참가자가 우선됩니다.
참가자의 상담 요청 정보가 주어질 때, 참가자가 상담을 요청했을 때부터 상담을 시작하기까지 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원을 정하려 합니다. 단, 각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.
접근법
- 각 유형 당 멘토는 무조건 한명 이상씩 있어야 함
- 상담 순서는 상담 요청 시간이 빠른 순서대로 진행
예를 들어 상담 유형이 총 3가지이고, 멘토 인원은 5명 일 때
무조건 유형당 한명씩은 존재해야 하기 때문에 5 - 3 = 2
[1,1,1]에서 2명을 추가해줘야 함
-> [1,1,3] , [2,2,1] , [3,1,1] .... 등등 총 합이 5를 충족하는 경우의 수가 나오는데(각 원소는 무조건 1 이상)
이때마다 대기시간을 구해서 그 중 가장 작은 값을 리턴
or
[1,1,1]에서 각 타입별로 대기시간을 구하는 것에서 출발해서
멘토 인원을 충족할 때 까지 가장 오래 걸리는 타입에 한명씩 추가해주는 걸 반복해주면 됨
function solution(k, n, reqs) {
//멘토 한명씩은 무조건
let required = n - k//기본값 1에서 추가해야 할 멘토
//mentor[type]으로 걸리는 시간
const result = []
const bfs = (arr) => {
if(arr.length >= k){
if(arr.reduce((v,i) => v + i ) === n){
const mentor = [1,...arr]
let sum = 0
for(let i=1;i<=k;i++){
sum += checkTime(i,mentor)
}
result.push(sum)
}
return}
for(let i=1;i<=n-k+1;i++){
bfs([...arr,i])
}
}
bfs([])
function checkTime (type,mentor) {
let waitingTime = 0
const line = Array(mentor[type]).fill(0)//각 멘토의 상담 종료시간
const filter = reqs.filter((v) => v[2] === type)
for(let req of filter){
line.sort((a,b) => a - b)
const [start,time,n] = req//상담 시작시간 , 상담 시간
if(line[0] < start){
//안기다리고 시작 가능
//끝나는 시간은 ?
line[0] = start+time
} else {
waitingTime += line[0] - start
line[0] += time
}
}
return waitingTime
}
return Math.min(...result)
}