[프로그레머스/Javascript] 상담원 인원

Node.js 백엔드 개발자로 진로를 정했다 보니, javascript를 사용한 코테도 준비해야겠다는 생각이 들었다. 기존에 준비하던 C++ 에서 js 에 적응하려다 보니 어려운 것이 한두가지가 아닌것 같다.

문제 분석

우선, 참가자들이 상담을 요청할 때 가능한 가장 빠른 시간에 상담을 받을 수 있도록 멘토를 배정해야 한다. 이 문제의 핵심은 각 상담의 종류별로, 가장 먼저 끝나는 상담 시간을 사용하는 것이다.

다음을 유의하여 풀어보자.

1. 맨토는 n 명이 있다
2. 상담의 종류는 k개가 있다
3. 멘토는 자신이 담당하는 유형의 상담 외에 다른 유형의 상담은 불가능 하다
4. 멘토는 한번에 한명만 상담이 가능하다
5. 상담이 끝났을때, 대기중인 인원이 있다면 해당 참가자와 상담을 시작한다.
6. 각 유형별로 멘토는 최소 1명 이상이어야 한다.

문제 접근법

그렇다면 최적의 배치 인원을 구할 수 있는 방법이 무엇일까?

필자는 dfs 를 통한 brute-force 방식밖에 떠오르지 않았다. (아마 bit-maksing으로도 되지 않을까?)

각 combination 이 정해진다면, 다시한번 완전탐색을 통해 각 combination 별로 대기 시간을 계산하여, 이 중 최솟값을 구해야 한다.

코드

function solution(k, n, reqs){

  function makeCombs(k, n, arr){
    let ret = [];
    if(n <= 0) return false;
    if(k === 1) return [[...arr,n]];
    for(let i = 1; i<n; i++){
      const attached = makeCombs(k - 1, n - i, [...arr, i]);
      if(!attached) return false;
      ret.push(...attached)
    }
    return ret;
  }
  const combinations = makeCombs(k,n,[]);

  let answer = Infinity;

  for(let combs of combinations){
    let counselorList = [];
    for(let i = 0; i<combs.length; i++){
      for(let j = 0; j<combs[i]; j++){
        counselorList.push({type : i + 1, end : 0});
      }
    }

    let totalTime = 0;

    for(let [start, duration, type] of reqs){
      let minCounselor = {end: Infinity};
      for(let counselor of counselorList){
        if(counselor.type === type && counselor.end < minCounselor.end){
          minCounselor = counselor;
        }
      }

      if(minCounselor.end > start){
        totalTime += minCounselor.end - start;
        minCounselor.end += duration;
      }else{
        minCounselor.end = start + duration;
      }
    }
    answer = answer < totalTime ? answer : totalTime;
  }

  return answer;
}