[프로그래머스] 상담원 인원

https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스

풀이과정

1. 유형 별 멘토의 숫자 조합을 다 구하기 (완전탐색)

    1-1. 이때 n은 최대 20이며 k는 최대 5입니다. 아래 설명에 정리를 해놓았는데 n-1개(19)에서 k-1개(4)의 조합을 뽑는 모든 경우는 3,876개 입니다.

    1-2. reqs의 길이는 최대 300이므로, 모든 조합에서 지연시간을 계산하는 경우는 3876*300 =1,162,800 입니다.

    1-3. 즉 완전탐색 해도 시간초과가 발생하지 않습니다.

2. 우선순위 큐를 활용하여 지연시간 계산하기

3. 최솟값 갱신하기

 

설명

유형 별 멘토의 숫자 조합을 구하는 방법

예) 5명의 상담원과 3가지의 상담유형이 있는 경우

• 검은색 원이 상담원이라고 할 때, 파란색 막대기를 놓을 수 있는 위치 (1번~4번) 에서 두 개를 조합(combination)하는 경우 입니다.
• 즉 n,k로 표현을 하자면 1~n-1의 숫자 중 k-1개의 조합을 뽑는 것 입니다.

위 그림에서 1~4 숫자 중 2개를 뽑는 조합의 경우는

1,2

1,3

1,4

2,3

2,4

3,4

이며,

 

1,4의 경우를 표현하면 아래 그림과 같아집니다.

 

즉, 1번 유형은 1명 2번 유형은 3명 3번 유형에는 1명을 배치하게 되는 것 입니다.

 

코드로 나타내면 아래와 같습니다.

...

int[] comb = new int[k-1]; // 설명을 위해서 변수를 밖으로 뺐음

void solve(int cnt, int start){
        if(cnt==k-1){
            System.out.println(Arrays.toString(comb));
            return;
        }
        
        for(int i=start;i<n;i++){
            comb[cnt] = i;
            solve(cnt+1,i+1);
        }
        
}

...

• solve함수를 통해서 재귀적으로(백트래킹? dfs?) 완전탐색합니다.
• cnt매개변수로 현재 선택이 완료된 갯수를 넘겨주고, start매개변수로 다음 탐색 위치를 갱신해줍니다.
•  solve(cnt+1, i+1) 코드 다음 comb[cnt] = i를 원상복구 시켜주는 코드는 필요가 없습니다.
  • 왜냐하면 다음 탐색 때 해당 위치에 새로운 값이 덮어씌워지기 떄문입니다.

 

우선순위 큐를 활용하여 지연시간 계산하기

 

문제에서 주어진 예시(1번 유형 : 2명, 2번 유형 : 1명, 3번 유형 : 2명)에서

1번 유형 상담의 지연 시간을 계산해보겠습니다.

참가자 번호	시각	상담 시간	상담 유형
1번 참가자	10분	60분	1번 유형
3번 참가자	20분	30분	1번 유형
5번 참가자	50분	40분	1번 유형
7번 참가자	65분	30분	1번 유형

 

 

우선순위 큐를 활용한 계산을 그림으로 표현하면 아래와 같습니다.

 

0. 우선순위 큐의 초기 값(0분)의 갯수는 위에서 구한 유형 별 멘토의 숫자 조합의 결과로 초기화를 시켜줘야 합니다.

위 예시의 경우

1번 유형에 배치된 멘토는 2명 이므로 우선순위 큐에 0을 두 개 넣어서 초기화를 시켜줍니다.

2번 유형에 배치된 멘토는 1명 이므로 우선순위 큐에 0을 한 개 넣어서 초기화를 시켜줍니다.

3번 유형에 배치된 멘토는 2명 이므로 우선순위 큐에 0을 두 개 넣어서 초기화를 시켜줍니다.

 

1. 초기 우선순위 큐는 0이 2개 들어가있도록 초기화 합니다.

2. 최솟값을 pollFirst()하면 0분이 나옵니다.

1번 참가자의 시각 10분 보다 작은 값이므로 지연이 발생하지 않습니다.

 

3. 1번 참가자의 상담이 끝날 시각 (10분 + 60분)을 offer해줍니다.

4. 다음 상담을 위해 최솟값을 pollFirst()합니다.

0분은 3번 참가자의 시각 30분 보다 작은 값이므로 지연이 발생하지 않습니다.

 

5. 3번 참가자의 상담이 끝날 시각 (20분 + 30분)을 offer해줍니다.

 

6. 다음 상담을 위해 최솟값을 pollFirst()합니다.

50분은 5번 참가자의 시각 50분 과 같은 값이므로 지연이 발생하지 않습니다.

 

7. 5번 참가자의 상담이 끝날 시각 (50분 + 40분)을 offer해줍니다.

 

8. 다음 상담을 위해 최솟값을 pollFirst()합니다.

70분은 7번 참가자의 시각 65분 보다 큰 값이므로 지연이 발생합니다. 

70분-65분=5분. 즉 5분의 지연이 발생하게 됩니다.

 

모든 경우가 끝났습니다.

 

위 예시의 경우 총 5분의 지연이 발생하게 됩니다.

 

이렇듯 우선순위 큐를 활용해서 지연 시간을 계산할 수 있습니다.

 

알게된 점

• 유형 별 할당될 인원의 갯수를 구하는 부분을 조합을 통해서 구현할 수 있음을 알게 되었습니다. 이 부분이 영어로는 stars and bars인 것 같습니다.

https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Stars and bars (combinatorics) - Wikipedia

• 조합을 구할 때 원상복구 로직이 필요없음을 다시 한 번 공부할 수 있었습니다.

 

전체코드

import java.util.*;

// 1. 1~n-1 의 숫자 중 k-1개의 조합을 뽑기
// 1-1. 뽑아진 조합 숫자들의 차이 값을 통해서 유형 별 멘토의 숫자를 구하기
// 2. 그 결과 값을 바탕으로 PQ의 초기 원소 갯수 설정
// 3. PQ를 활용해서 지연시간 누적하기
// 4. 최솟값 갱신하기
class Solution {
    
    static final int INF = (int)1e9;
    int[] comb;
    int answer;
    int k,n;
    int[][] reqs;
    PriorityQueue<Integer>[] pq;
    
    
    int calc(){
        int result = 0;
        
        for(int[] req : reqs){
            int a = req[0]; // a분에
            int b = req[1]; // b분 동안
            int c = req[2]-1; // c유형의 상담
            
            int d = pq[c].poll(); // 현재 pq에 가장 빠르게 끝나는 상담 시간
            
            if(d - a > 0){ // 대기해야 하면
                result += (d - a);
                pq[c].offer(d + b);
            }else{ // 대기 하지 않아도 되면
                pq[c].offer(a + b);
            }
        }
        
        return result;
            
    }
    
    void solve(int cnt, int start){
        if(cnt==k-1){
            
            for(int i=0;i<k;i++){
                pq[i] = new PriorityQueue<>();
            }
            
            // comb[0], comb[1], ... , comb[k-2]
            for(int i=0;i<comb[0];i++){
                pq[0].offer(0);
            }
            
            for(int i=1;i<k-1;i++){
                for(int j=comb[i-1];j<comb[i];j++){
                    pq[i].offer(0);
                }
            }
            
            for(int i=comb[k-2];i<n;i++){
                pq[k-1].offer(0);
            }
            
            answer = Math.min(answer,calc()); // 최솟값 갱신
            
            return;
        }
        
        for(int i=start;i<n;i++){
            comb[cnt] = i;
            solve(cnt+1,i+1);
        }
        
    }
    
    
    public int solution(int k, int n, int[][] reqs) {
        
        answer = INF;
        this.k = k;
        this.n = n;
        this.reqs = reqs;
        pq = new PriorityQueue[k];
        
        if(k==1){ // k==1 인 경우 예외처리
            pq[0] = new PriorityQueue<>();
            
            for(int i=0;i<n;i++){
                pq[0].offer(0);
            }
            answer = Math.min(answer,calc());
            return answer;
        }
        
        comb = new int[k-1];
        
        solve(0,1);
        
        return answer;
    }
}