프로그래머스 상담원 인원 python, java

조합으로 모든 경우의 수를 구해서 풀이해봤는데 시간내에 들어올 수 있었다.

📜 문제 바로 가기 : 상담원 인원

제출코드

파이썬

import heapq

def solution(k, n, reqs):
    ans = 2 << 31
    
    n -= k
    
    arr = [1] * (k+1)
    def recur(s, last):
        nonlocal arr
        
        if s == n:
            calculator(arr)
            return
        
        for e in range(1, n+1):
            for i in range(last+1, k+1):
                arr[i] += e
                recur(s+e, i)
                arr[i] -= e
                
    def calculator(lst):
        nonlocal ans
        time = 0
        con = [[] for _ in range(k+1)]
        for i in range(1, k+1):
            for _ in range(lst[i]):
                heapq.heappush(con[i], 0)
                
        for (a, b, c) in reqs:
            t = heapq.heappop(con[c]) # 상담 가능한 가장 빠른시간
            if t <= a:
                heapq.heappush(con[c], a+b)
            else:
                heapq.heappush(con[c], t+b)
                time += (t-a)
                if time >= ans:
                    return

        ans = time
            
            
    recur(0, 0)

    return ans

자바

import java.util.*;

class Solution {
    static int k;
    static int n;
    static int[][] reqs;
    static int [] arr;
    static int ans = (int) Math.pow(2, 31) -1;
    
    public int solution(int k, int n, int[][] reqs) {
        Solution.k = k;
        Solution.n = n - k;
        Solution.reqs = reqs;
        Solution.arr = new int[k+1];
        
        for (int i = 1; i < k+1; i++) {
            arr[i] = 1;
        }
        
        Solution.recur(0, 0);
        
        return Solution.ans;
    }
    
    public static void recur(int s, int last) {
        if (s == Solution.n) {
            Solution.calculator();
            return ;
        }
        
        for (int i = 1; i <= Solution.n; i++) {
            for (int j = last+1; j <= Solution.k; j++) {
                Solution.arr[j] += i;
                Solution.recur(s+i, j);
                Solution.arr[j] -= i;
            }
        }
        
    }
    
    public static void calculator() {
        PriorityQueue<Integer> [] con = new PriorityQueue [k+1];
        int time = 0;
        for (int i = 0; i < k+1; i++) {
            con[i] = new PriorityQueue<Integer>();
            for (int j = 0; j < arr[i]; j++) {
                con[i].add(0);
            }
        }
        
        for (int i = 0; i < Solution.reqs.length; i ++) {
            int a = Solution.reqs[i][0];
            int b = Solution.reqs[i][1];
            int c = Solution.reqs[i][2];
            int t = con[c].poll();
            if (t <= a ) {
                con[c].add(a+b);
            } else {
                con[c].add(t+b);
                time += (t-a);
                if (time >= Solution.ans) {
                    return ;
                }
            }
        }

        Solution.ans = time;
    }
}

---

접근방법

recur()

recur() 재귀함수를 통해서 모든 경우의 조합을 구한다. 조합을 통해서 상담원 배치 인원정보 배열 arr이 구해지면 최소 대기시간을 구하는 calculator() 함수로 계산이 넘어가진다.

calculator()

calculator() 에서는 대기간을 구하게 되는데 con 배열에는 각 인덱스 번호에 해당하는 상담원이 상담 가능한 시간정보가 들어있다. 상담 신청이 들어왔을 때, 그 상담유형의 그룹 con[c] 에서 상담 가능시간이 가장 빠른 시간을 뽑아야한다. 이를 위해서

• 정렬
• 우선순위큐

이 두가지 방법이 있을거 같은데 나는 여기서 우선순위큐인 heapq 를 사용했다. (자바는 PriorityQueue)
heapq를 통해 상담 가능한 가장 빠른시간(t)을 뽑아내고 상담 희망시간(a) 보다 빠르다면 바로 a+b 값을 추가해주면 되지만 늦다면 대기시간(t-a)이 발생하고 t+b 값을 추가해 주면 되겠다.