정답 코드

from collections import defaultdict
import heapq
from copy import deepcopy
from itertools import product


def solution(k, n, reqs):
    reqs.sort(key = lambda x: x[0], reverse=True)
    infos = defaultdict(list)
    for a, b, c in reqs:
        infos[c].append((a, b))
    max_con = n - k + 1

    def cal_time(n, tp):  # n = 상담원 수, type = 유형 => type유형에 상담원이 n명일 때 기다리는 시간
        m = n
        queue = deepcopy(infos[tp])
        total = len(queue)
        on_going = []
        heapq.heapify(on_going)
        complete = 0
        waiting = 0
        while complete < total:
            if len(on_going) == 0:
                while m > 0 and len(queue) > 0:
                    start, duration = queue.pop()
                    heapq.heappush(on_going, start + duration)
                    m -= 1
                    complete += 1
            else:
                time = heapq.heappop(on_going)
                m += 1
                while m < n and len(on_going) > 0 and on_going[0] == time:
                    heapq.heappop(on_going)
                    m += 1
                while m > 0 and len(queue) > 0:
                    start, duration = queue.pop()
                    if time > start:
                        waiting += time - start
                        heapq.heappush(on_going, time + duration)
                    else:
                        heapq.heappush(on_going, start + duration)
                    complete += 1
                    m -= 1

        return waiting

    
    board = [[0] for _ in range(k + 1)]
    for tp in range(1, k + 1):
        if tp in infos:
            for m in range(1, max_con + 1):
                board[tp].append(cal_time(m, tp))
        else:
            board[tp] = [0] * (max_con + 1)

    answer = []
    combs = product(range(1, n - k + 2), repeat=k)
    for comb in combs:
        if sum(comb) == n:
            tmp = 0
            for i in range(k):
                tmp += board[i + 1][comb[i]]
            answer.append(tmp)
    
    return min(answer)

---

풀이 방향

각 상담 유형 별로 상담원이 n명 있을 때 총 기다리는 시간이 몇 분인지를 미리 계산해 놓는다!

상담 유형 별로 최소 1명씩 있어야 한다.
테스트케이스 1번의 경우 상담원이 배치되는 경우는
(1,1,3)
(1,2,2)
(1,3,1)
(2,1,2)
(2,2,1)
(3,1,1)

총 6가지이다.

위의 6가지에 대해서 전부 값을 계산하고 그 중에 최솟값을 최종 정답으로 선정해야한다.

그렇다면 tp번 상담 유형에 n명의 상담원이 배치 됐을 때 상담 기다림 시간을 구하여 미리 배치해놓고 위의 6가지에 대해 미리 계산한 값을 사용한다면 시간을 단축할 수 있다!!

그 기다리는 시간을 계산하는 함수가 위의 코드에서의
cal_time(n, tp)
이다.

풀이 방법

cal_time(n, tp)

m = n
queue = deepcopy(infos[tp])
total = len(queue)
on_going = []
heapq.heapify(on_going)
complete = 0
waiting = 0

여기서

m: 현재 비어있는 상담원 수
queue: 기다리는 손님
on_going: 현재 상담받고 있는 사람의 끝나는 시각
complete: 상담 받으러 들어간 사람 수
waiting: 총 기다린 시간

if len(on_going) == 0:
	while m > 0 and len(queue) > 0:
    	start, duration = queue.pop()
    	heapq.heappush(on_going, start + duration)
    	m -= 1
    	complete += 1

이 부분은 처음, 즉 상담원이 모두 available할 때의 경우입니다.
3명의 상담원이 배치됐다면 기다리는 손님 중 시간 순서대로 3명을 뽑아서 on_going 에 넣어줍니다.

time = heapq.heappop(on_going)
m += 1
while m < n and len(on_going) > 0 and on_going[0] == time:
	heapq.heappop(on_going)
    m += 1
while m > 0 and len(queue) > 0:
	start, duration = queue.pop()
    if time > start:
    	waiting += time - start
        heapq.heappush(on_going, time + duration)
    else:
    	heapq.heappush(on_going, start + duration)
    complete += 1
    m -= 1

이 부분은 처음 이후의 단계입니다.

1. 우선 시각을 상담 받는 사람 중 가장 빨리 끝나는 사람의 시각으로 맞춰줍니다.
   time = heapq.heappop(on_going)

2. 한명의 상담이 끝났으니 available한 상담원 수를 1 늘려줍니다.
   m += 1

3. 같은 시각에 상담이 끝나는 사람들이 더 있을 수 있으니 모두 on_going에서 제거해줍니다. 이 때 m(가능한 상담원 수)이 n(총 상담원 수)을 넘지 않도록 해줍니다.

while m < n and len(on_going) > 0 and on_going[0] == time:
	heapq.heappop(on_going)
	m += 1

4. 이제 추가해 줄 차례입니다. 가능한 많이 queue에서 on_going으로 이동시킬겁니다. 여기서 기다리는 사람의 상담 시작시각(start)이 위의 time보다 이르다면 기다린 것이므로 waiting을 time - start만큼 늘려줍니다. 끝나는 시각은 현재 시각인 time에 duration을 더한 값을 on_going에 추가해줍니다.
   상담 시작시각(start)이 위의 time보다 늦거나 같다면 기다리지 않았기 때문에 on_going에는 끝나는 시각인 start + duration 을 추가해줍니다.

while m > 0 and len(queue) > 0:
	start, duration = queue.pop()
    if time > start:
    	waiting += time - start
        heapq.heappush(on_going, time + duration)
    else:
    	heapq.heappush(on_going, start + duration)
complete += 1
m -= 1

---

값들을 미리 계산하지 않아도 시간 초과가 나지 않는 케이스들로만 구성된 것 같긴 하지만 항상 최적의 코드를 생각해야겠죵?!

---

---

function solution(k, n, reqs) {
  reqs.sort((a, b) => b[0] - a[0])
  const infos = {};
  reqs.map(item => {
    let [a, b, c] = item;
    if (!(c in infos)) {
      infos[c] = [[a, b]];
    } else {
      infos[c].push([a, b]);
    };
  });
  const maxCon = n - k + 1;

  function cal_time(n, tp) {
    let m = n;
    const queue = JSON.parse(JSON.stringify(infos[tp]));
    const total = queue.length;
    const onGoing = [];
    let complete = 0;
    let waiting = 0;
    while (complete < total) {
      if (onGoing.length === 0) {
        while (m > 0 && queue.length > 0) {
          const [start, duration] = queue.pop();
          onGoing.push(start + duration);
          onGoing.sort((a, b) => a - b);
          m--;
          complete++;
        }
      } else {
        const time = onGoing.shift();
        m++;
        while (m < n && onGoing.length > 0 && onGoing === time) {
          onGoing.shift();
          m++;
        };
        while (m > 0 && queue.length > 0) {
          const [start, duration] = queue.pop();
          if (time > start) {
            waiting += time - start;
            onGoing.push(time + duration);
          } else {
            onGoing.push(start + duration);
          };
          onGoing.sort((a, b) => a - b);
          complete++;
          m--;
        }
      }
    }
    return waiting;
  };

  const board = Array(k + 1).fill().map(() => [0]);
  for (let tp = 1; tp < k + 1; tp++) {
    if (tp in infos) {
      for (let m = 1; m < maxCon + 1; m++) {
        board[tp].push(cal_time(m, tp));
      }
    } else {
      board[tp] = Array(maxCon + 1).fill().map(() => 0);
    };
  };

  function cartesian(args) {
    if (args.length === 0) return [[]];
    let prod = cartesian(args.slice(1));
    let r = [];
    args[0].forEach(function(x) {
      prod.forEach(function(p) {
        r.push([x].concat(p));
      });
    });
    return r;
  }
  
  const arr = Array.from({length: n - k + 1}, (_, i) => i + 1);
  const args = Array(k).fill(arr);
  const combs = cartesian(args);

  const answer = [];
  combs.forEach(item => {
    const sum = item.reduce((acc, curr) => acc + curr, 0);
    if (sum === n) {
      let tmp = 0;
      item.forEach((item2, idx) => {
        tmp += board[idx + 1][item2];
      });
      answer.push(tmp);
    }
  })


  return Math.min(...answer)
}