[JS] 상담원 인원

문제를 처음 딱 읽고 보니 완전탐색이 떠올랐다.

어차피 유형이 최대 5개이니 

 

합이 n이 나오는 5개의 수 조합을 찾으면 되는 문제였다.

 

몇번 공부했었던 combination을 구하는 로직을 조금 비틀어서 위 수식을 구한 이후에는 시나리오들을 돌려보며 time들을 구하면 되는 문제이다.

 

어떻게 풀까 하다가 객체를 통해서 문제를 해결하기로 했다. 상담자 객체를 하나 만들어서 상담이 종료되는 시각과 타입이 들어온다.

 

문제에서 상담원들은 시간순서대로 들어오기 때문에

 

1. 상담받을수 있는 상담가 중에서 종료 시간이 가장 최근인 상담가를 선택

 

종료시간이 현재보다 과거라면 지금당장 상담을 받을 수 있기에 상담가의 종료시간을 현재시간 + 상담기간으로 설정

종료시간이 현재보다 미래라면 지금당장 상담 받을 수 없기에 상담가의 종료시간을 종료시간 + 현재시간으로 설정하고 delay시간에 상담가의 현재 종료시간 - 현재시간만큼 더해준다.

 

각 조합별로 이들을 누적한 값들 중 가장 작은값이 정답이다.

 

 

 

문제푸는것 자체는 큰 무리가 없었으나 시간이 1000초까지인줄 알고 초기값을 1000으로 두어서 문제를 해결하지 못했다. 10000으로 넘겼더니 대부분의 케이스는 통과했는데 케이스 중에서 더 큰 케이스가 있는지 Infinity로 초기값을 두니 무사히 통과했다.

 

 

 

const getAry = (n, k, ary) => {
  let ret = [];
  if (n <= 0) return false;
  if (k === 1) return [[...ary, n]];
  for (let i = 1; i < n; i++) {
    const attached = getAry(n - i, k - 1, [...ary, i]);
    if (!attached) break;
    ret.push(...attached);
  }

  return ret;
};

function solution(k, n, reqs) {
  const combination = getAry(n, k, []);

  let ret = Infinity;

  for (const combi of combination) {
    const counselorAry = [];
    combi.forEach((el, idx) => {
      for (let i = 0; i < el; i++) {
        counselorAry.push({
          type: idx + 1,
          end: 0,
        });
      }
    });

    let time = 0;
    for (const [start, period, type] of reqs) {
      let minCounselor = {
        end: Infinity,
      };
      for (const counselor of counselorAry) {
        if (counselor.type === type && counselor.end < minCounselor.end) {
          minCounselor = counselor;
        }
      }

      if (start < minCounselor.end) {
        time += minCounselor.end - start;
        minCounselor.end = minCounselor.end + period;
      } else {
        minCounselor.end = start + period;
      }
    }
    ret = time < ret ? time : ret;
  }
  return ret;
}