[programmers/js] 상담원 인원

상담원 인원

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

문제 설명

상담원 인원 배정 문제는 주어진 시간 동안 각 멘토가 여러 명의 상담을 처리하는 방식으로, 상담원이 주어진 시간 내에 효율적으로 배치되도록 해야 합니다. 여기서 중요한 점은 각 멘토가 담당하는 상담의 시작과 종료 시간이 주어졌을 때, 최소 대기 시간을 계산하는 것입니다.

풀이

문제 분석

• 각 멘토가 처리할 상담에 대해 시작 시간과 종료 시간이 주어집니다.
• 각 멘토가 상담을 완료하는 데 걸리는 시간이 최소화되도록 멘토를 배정해야 합니다.
• 중복된 배정 조합을 피해야 하며, 가능한 모든 배정을 탐색해야 합니다.

문제 해결을 위한 접근법

• 가능한 배정 조합을 DFS를 이용해 구합니다.
• DFS가 깊이 들어가면서 상담원의 배정 조합을 구하고, 그 조합에 대한 시뮬레이션을 실행하여 최소 대기 시간을 계산합니다.

1. type별로 인원 분리
   상담 타입에 맞게 인원을 분리합니다.

const byType = {};
for (const [start, duration, type] of reqs) {
  if (!byType[type]) byType[type] = [];
  byType[type].push([start, start + duration]);
}

2. 상담 배정 조합 생성
   DFS를 통해 각 상담원이 담당할 상담 수를 탐색합니다. 이때 assign 배열을 이용해 각 멘토가 담당할 상담 수를 기록합니다.

const dfs = (idx, sum, assign) => {
  if (idx === k) {
    if (sum === n) simulator(assign);
    return;
  }

  for (let cnt = 1; cnt <= n - (k - idx - 1); cnt++) {
    assign[idx] = cnt;
    dfs(idx + 1, sum + cnt, assign);
  }
};

dfs(0, 0, Array(k).fill(0));

3. 상담 배정 시뮬레이션
   각 배정에 대해 mentors 배열을 이용해 멘토들이 상담을 처리하는 과정을 시뮬레이션합니다. mentors 배열의 각 원소는 멘토가 처리 중인 상담의 종료 시간을 나타냅니다.

const simulator = (assign) => {
  let totalWait = 0;

  for (let i = 1; i <= k; i++) {
    const mentors = Array(assign[i - 1]).fill(0); // 배정된 멘토 만큼 배열 생성
    const reqList = byType[i] || [];

    reqList.sort((a, b) => a[0] - b[0]); // 시작 시간 기준 정렬

    for (const [start, end] of reqList) {
      mentors.sort((a, b) => a - b); // 가장 빨리 끝나는 상담사 찾기
      const earliest = mentors[0];

      if (earliest <= start) {
        mentors[0] = end;
      } else {
        totalWait += earliest - start;
        mentors[0] = earliest + (end - start);
      }
    }
  }
  minTime = Math.min(minTime, totalWait);
}

최종 코드

function solution(k, n, reqs) {    
    // type별 분리
    const byType = {};
    for (const [start, duration, type] of reqs) {
      if (!byType[type]) byType[type] = [];
      byType[type].push([start, start + duration]);
    }

    let minTime = Infinity; // 최소 시간
    const simulator = (assign) => {
        let totalWait = 0;

        for (let i = 1; i <= k; i++) {
            const mentors = Array(assign[i - 1]).fill(0); // 배정된 멘토 만큼 배열 생성
            const reqList = byType[i] || [];
            
            reqList.sort((a, b) => a[0] - b[0]); // 시작 시간 기준 정렬

            for (const [start, end] of reqList) {
                 mentors.sort((a, b) => a - b); // 가장 빨리 끝나는 상담사 찾기
                 const earliest = mentors[0];

                 if (earliest <= start) {
                    mentors[0] = end;
                 } else {
                    totalWait += earliest - start;
                    mentors[0] = earliest + (end - start);
                }
            }
        }
        minTime = Math.min(minTime, totalWait);
    }
    
    const dfs = (idx, sum, assign) => {
        if (idx === k) {
            if (sum === n) simulator(assign);
            return;
        }

        for (let cnt = 1; cnt <= n - (k - idx - 1); cnt++) {
            assign[idx] = cnt;
            dfs(idx + 1, sum + cnt, assign);
        }
    };

    dfs(0, 0, Array(k).fill(0));
    
    return minTime
    
}