[JS] 상담원 인원

문제

프로그래머스

 

풀이

이 문제는 오늘 서류 합격된 회사 코테를 보며 못푼 문제여서 분해서 풀게된 문제다....(분하다...)

 

이 문제는 각 상담원의 조합들 중 최적의 조합을 선택하는 문제이다. 상담의 종류가 최대 5개이고 상담건수가 최대 300개 이기 때문에 완전 탐색을 진행해도 시간복잡도가 여유로운 편이다.

아오 이걸 테스트때 이상한 방법으로 접근했어....

 

조합을 구했다면 각 상담원의 인원수에 맞게 총 걸린시간과 상담 종류를 갖는 자료를 만든다.

이 자료를 사용하며 구현해야 하는 조건은 다음과 같다.

 

우선 대기중인 인원은 끝나는 시간이 가장 빠른 상담원과 연결된다. 그 다음은 시간 계산이 있다.

시간 계산의 경우 신청한 시간이 끝나는 시간보다 빠르다면 끝나는 시간 + 상담 시간이 그 사람의 상담이 끝나는 시간이며, 신청한 시간이 더 느리다면 그 사람의 상담이 끝나는 시간은 신청 시간 + 상담 시간이 된다.

 

코드

const getComb = (k, n, arr) => {
  const res = [];
  if (n <= 0) return false;
  if (k === 1) return [[...arr, n]];
  for (let i = 1; i < n; i++) {
    const temp = getComb(k - 1, n - i, [...arr, i]);
    if (!temp) break;
    res.push(...temp);
  }
  return res;
}

function solution(k, n, reqs) {
  const combs = getComb(k, n, []);
  let answer = Infinity;

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

    for (let [st, req, type] of reqs) {
      let mintemp = {
        end: Infinity
      };

      // 이건 됨
      for (const t of temp) {
        if (t.type === type && t.end < mintemp.end) {
          mintemp = t;
        }
      }

      // 이건 안됨
      // if(temp[type - 1].end < mintemp.end){
      //     mintemp = temp[type - 1];
      // }

      if (st < mintemp.end) {
        totalTime += mintemp.end - st;
        mintemp.end = mintemp.end + req;
      }
      else {
        mintemp.end = st + req
      }
    }
    if (answer > totalTime) answer = totalTime;
  }
  return answer;
}