[5주차_목요일] 상담원 인원

[yeongleej]

• 사이트 : 프로그래머스(PG)
• 문제: 상담원 인원
• 번호: 214288

[yeongleej]

🤔 시간복잡도 고려사항

• 1 ≤ k ≤ 5

• k ≤ n ≤ 20

• 3 ≤ reqs의 길이 ≤ 300

• [중복순열] 유형별로 상담원 분배하기 : O(n^k) == 20^5 약, 3,200,000

• [우선순위큐] 상담하기 : 상담자 수 * 해당 유형의 상담자 중 가장 빨리 끝나는 상담자 찾기

  • 최대 상담자 수 reqs: 300
  • 최대 상담원 수 m: 20 => O(reqs * mlogm) : 가능

💡 풀이 아이디어

1. 상담원 분배하기 => 중복순열

   • 총 n명의 상담원을 k개의 유형으로 분배해야함
   • 예) 4명, 3개 유형 => [1, 1, 2], [1, 2, 1] [2, 1, 1] ,,,,,,,
   • 중복순열 시간복잡도 : O(n^k)

2. 상담하기 => 우선순위큐 이용

   • mento[] : 각 유형별로 우선순위큐를 이용해 가장 상담이 빨리 끝나는 상담사 출력
     • 즉, 우선순위큐 배열임
   • 초기화
     • mento[i]에는 위의 상담원 분배에서 분배한 상담사의 수 만큼 0으로 초기화
     • 0은 각 상담사의 끝나는 시간을 의미함
     • 상담사 선택 : endTime = mento[i].poll()
     • 기다린 시간 계산
       • waitTime : (출력된 상담사의 끝나는 시간 - 멘티의 시작시간)
       • 이는 기다리지 않으면 음수값이 되므로 max(0, waitTIme) 으로 기다리지 않았다면 0으로 처리
     • 다시, 현재 유형에 멘티의 상담 끝나는 시간을 add 해서 상담원 인원수 맞춤

[Jewan1120]

🤔 시간복잡도 고려사항

• k ≤ n ≤ 20 → 순열 가능할 듯

💡 풀이 아이디어

• 멘토들을 배치할 수 있는 모든 조합을 만들며 계산
  • 유형 별 멘토의 수가 중복되서 나오기 때문에 미리 대기 시간을 계산해두면 좋을듯
• 멘토 유형 별, 인원 수에 따라 걸리는 시간을 계산
  • 우선 순위 큐를 이용해서 상담 중인 인원이 끝나는 시간을 오름차순으로 저장
  • 다음 인원이 상담을 시작할 때
    • 한가한 멘토가 있을 경우 바로 상담 시작 ※대기시간 없음
    • 그렇지 않다면 일찍 끝나는 인원의 종료 시간에 따라 다음 인원의 대기 시간 및 종료 시간 계산

      // 만들 수 있는 모든 멘토의 조합을 구함
      // @param remainig : depth번 째 유형에 사용할 수 있는 멘토의 수
      private void makeConsultCombi(int k, int remaining, int depth) {
      // 마지막 유형의 멘토까지 왔다면 남은 인원들 전부 추가 후 총 대기시간 계산
      if (depth == k) {
      consultCombi[depth] += remaining;
      int totalWaitingTime = 0;
      // 미리 계산한 대기 시간표로 총 대기 시간을 계산
      for (int i = 1; i < k + 1; i++) {
      totalWaitingTime += waitingTimes[i][consultCombi[i]];
      }
      minWaitingTime = Math.min(minWaitingTime, totalWaitingTime);
      consultCombi[depth] -= remaining;   // 백 트래킹
      return;
      }
      for (int i = 1; i < remaining; i++) {
      consultCombi[depth] += i;   // depth번 째 유형에 i만큼의 멘토를 추가
      makeConsultCombi(k, remaining - i, depth + 1);  // 남은 멘토들로 다음 유형 탐색
      consultCombi[depth] -= i;   // 백 트래킹
      }
      }
      // 1 1 3 
      // 1 2 2 
      // 1 3 1 
      // 2 1 2 
      // 2 2 1 
      // 3 1 1 

      순열 만드는 거 빡셌네요

[baexxbin]

🤔 시간복잡도 고려사항

• k ≤ n ≤ 20
• 3 ≤ reqs의 길이 ≤ 300
• 조합 가능: 15C5 (3003) * 300

💡 풀이 아이디어

• counsel : 상담 유형 별 상담 분리하기

• dp : 각 상담 별로 (1~최대가능)상담원을 분배했을때 대기 시간 구하기

  • dp[i][j]: (i:상당유형, j:상담자 수)
  • 최대 상담자 수= n-k+2(현재 유형(1)+0부터시작(1))
  • 우선순위 큐 이용
    • 큐 크기는 상담자 수 만큼 유지되어야 함
    • 대기시간은 참가자 신청 시작시간보다 앞타임이 늦게 끝날때만 발생

• dfs : 조합으로 최소 대기 시간을 가지는 상담자 배분 구하기

  • dfs(int depth, int cns, int k) // 깊이(상담유형), 남은 상담자 수, 상담유형 개수
  • memo로 메모리제이션

조합 구현하기 더 연습하기,, 처리해야할 일이 뭉탱이로 주어지는거 잘 분리하기,,

[KodaHye]

🤔 시간복잡도 고려사항

• 멘토 인원을 적절히 배정했을 때, 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 최소값을 구해야 되는 문제
  • 유형별로 멘토 인원이 한 명 이상이 되어야 하므로 k개의 자연수를 더했을 때, n이 되어야 함 → 백트레킹을 통해 모든 경우 확인
  • 1 <= k <= 5, k <= n <= 20이므로 모든 경우 확인해도 시간 충분

💡 풀이 아이디어

• 백트레킹을 통해 k개의 자연수를 더했을 때, n이 되는 모든 경우를 확인해줌
• k개의 자연수를 더했을 때, n이 되는 경우
  • 대기 시간을 구함

처음엔 그냥 그리디,, 로만 풀 수 있을 줄 알았는데, 각 유형별로 멘토 인원이 한 명 이상이 되어야 하는 조건도 있고, 완탐으로 해야되더라구요!!,,, 역시 문제를 잘 읽어서 이해하고,, 잘 물어야겠다고 생각했습니다!

[yeahdy]

💡 풀이 아이디어

• 알고리즘: PriorityQueue+ 구현
• 시간복잡도: 3 ≤ reqs의 길이 ≤ 300 으로 단순구현 가능

🤔 시간복잡도 고려사항

• 유형별 최소 대기시간 계산에 따라 최적의 멘토 인원 분배 수를 찾고, 최소시간 계산하기
• 유형별 멘토 인원 분배 방법
  • PriorityQueue를 사용해서 여러 작업에서 가장 빨리 완료할 수 있는 작업부터 처리하기
  • 여러 작업: 유형별 상담 요청
  • 가장 빨리 완료: 상담종료 시간이 가장 적은 사람부터 처리
  • 기다리는 시간을 계산하고, 상담 종료 시 다음 상담요청 배치

[icegosimperson]

🤔 시간복잡도 고려사항 시간 복잡도 : n: 20, k=5 -> 주어진 조건 내 가능

💡 풀이 아이디어

• n명의 멘토 뽑아 k개의 유형으로 나눔(순서 나중에 생각) -> 조합
• n명의 멘토를 k개의 유형에 최소 한 명씩 배정 -> 재귀적으로 멘토 배정 조합 생성
• 주어진 멘토 배정 조합에 각 상담 유형별 대기 시간을 PriorityQueue로 대기 시간 합산
• 해당 유형의 멘토들 중 가장 빨리 상담 가능한 멘토 선택하여 대기 시간 계산 -> 다음 상담 가능 시간 업데이트 mentors.offer(Math.max(start, next) + ing);

조합 문제,,!! 처음 풀어봤는데 어렵네요 ㅠ_ㅠ 많이 풀어보겠습니다!