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

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스

🔍  해결 과정

처음에 문제를 보면서 들었던 생각은 k개마다 상담원들을 하나씩 배치를 완료하고 k개의 유형마다 (n - k)명의 상담원들을 중복 선택하는 중복 조합을 적용하여 상담원들을 배치했을 때 총 대기시간을 구한 다음 적절한 최소 대기 시간을 추출하는 방식이었습니다. 그러나 이 방식은 모든 경우를 다 돌아보면서 계속 최종 대기 시간을 구하기에는 시간적인 오류가 있었습니다. k개의 유형을 (n - k)번 중복 선택하는 중복 조합 공식을 적용해보면 최악의 경우 H(k, (n - k)) = (k + (n - k) - 1)C(n - k) = 약 15000의 연산량이 나옵니다. 배치만 했을 때의 연산량이 15000정도가 나오면 이후에 대기 시간을 계산시에도 많은 연산량이 겹쳐서 나올 것 같다는 생각을 하게 되었습니다.

 

그래서 좀 더 최적화 할 수 있는 방안을 고민했는데 그 방법은 모든 유형별로 상담원을 하나씩 배정해보면서 나올 수 있는 최종 대기 시간의 최솟값을 구하며 상담원의 최종 유형 배치를 완료하는 것입니다. 해결 과정의 내용은 다음과 같습니다.

1️⃣ 멘토 인원 배치 정보를 활용하기 위해서 int 배열의 types를 생성한다. 모든 유형마다 상담원을 한 명씩 가져야 하므로 types의 값들을 1로 초기화해준다.
2️⃣ 남은 (n - k)명의 상담원들을 k개의 유형에 적절하게 배치해주기 위해서 반복문을 활용하여 types의 특정 유형에 상담원을 한 명 추가했을 때의 최종 대기 시간의 최솟값이 나오는 적절한 유형을 정한다.
3️⃣ 적절한 유형에 상담원들을 모두 배치가 완료가 되었으면 최종 대기 시간을 구해준다.

 

상담원들을 배치했을 때 최종 대기 시간을 구하는 getTotalWaitTime 메서드를 활용하였는데 대기 시간을 계산해주기 위해서는 종료 시간과 다음 상담 시간의 차이를 활용하여 대기 시간을 계산해주었습니다. 그리고 상담이 끝난 멘토는 곧바로 먼저 대기 중인 멘티를 먼저 상담을 진행해주어야 하므로 종료 시간이 빠른 순서를 우선으로 하는 우선순위 큐 자료구조도 활용하였습니다. 자세한 설명은 코드 주석에 첨부하였습니다.

---

✏️ 코드

⏰ 시간 복잡도: O((n - k) * k * k * (reqs의 길이))

/**
n: 상담원 인원
k: 상담 유형의 수 (1번 ~ k번)
reqs: 요청한 상담들 ([a(요청 상담 시작 시간), b(희망 상담 기간), c(희망 상담 유형)])

과정
1. 유형들은 적어도 하나의 상담사들을 가지고 있어야 함.
2. 그 외 상담사들을 한 명씩 모든 유형에 배치해보면서 최적의 상담 대기 시간이 나올 수 있도록 계속 확인하면서 배정하기
3. 최정 배정 완료 후 총 상담 대기 시간을 구할 수 있도록 하기
**/
import java.util.Arrays;
import java.util.Queue;
import java.util.PriorityQueue;

class Solution {
        
    public int solution(int k, int n, int[][] reqs) {
        // 1번 과정 진행
        int remainMento = n - k; // 유형들을 하나씩 배정하고 남은 상담원 수
        
        // 2번 과정 진행
        int[] types = new int[k + 1]; // 각 유형별 상담원의 수
        Arrays.fill(types, 1); // 상담원들을 최소 한명씩 가지고 있어야 함.
        
        while (remainMento > 0) {
            int idealTypeNumber = -1;
            int maxWaitTime = Integer.MAX_VALUE;
            
            // 유형별로 하니씩 상담원들을 배정하면서 최적의 시간을 도출해내기
            for (int i = 1; i <= k; ++i) {
                ++types[i]; // 특정 유형에 상담원을 하나 배치하기
                int waitTime = getTotalWaitTime(reqs, types, k);
                
                // 대기 시간 계산 후 최적의 대기 시간 산출할 유형 저장하기
                if (maxWaitTime > waitTime) {
                    maxWaitTime = waitTime;
                    idealTypeNumber = i;
                }
                
                --types[i];
            }
            
            ++types[idealTypeNumber];
            --remainMento;
        }
        
        // 3번 과정 진행
        return getTotalWaitTime(reqs, types, k);
    }
    
    private int getTotalWaitTime(final int[][] reqs, final int[] types, 
                                 final int k) {
        // types를 다 돌아보면서 시간들을 계산하기
        int totalWaitTime = 0;
        
        for (int i = 1; i <= k; ++i) {
            totalWaitTime += getWaitTime(reqs, types, i);
        }
        
        return totalWaitTime;
    }
    
    private int getWaitTime(final int[][] reqs, final int[] types, 
                            final int typeNumber) {
        // 특정 유형 typeNumber에서의 요청 대기 시간을 구하기 (종료 시간을 기점으로 해서 우선 순위 큐를 만들고 진행하기)
        Queue<Integer> pq = new PriorityQueue<>(); // 종료 시간을 담을 큐
        int resultWaitTime = 0;
        
        for (int[] req : reqs) {
            // {a, b, c} -> (상담 요청 시간, 상담 기간, 상담 유형)
            if (req[2] != typeNumber) {
                continue;
            }
            
            // 멘토가 전부 상담 중인지 아닌지 확인하기
            if (pq.size() < types[typeNumber]) {
                pq.offer(req[0] + req[1]);
                continue;
            }
            
            // 대기 시간 계산하기
            int offTime = pq.poll();
            resultWaitTime += Math.max(0, offTime - req[0]);
            pq.offer(Math.max(offTime, req[0]) + req[1]);
        }
        
        return resultWaitTime;
    }
}