프로그래머스 - 상담원 인원 (Java)

구현, 그리디 문제입니다.

 

상담원 인원과 참가자의 상담 요청 정보가 주어졌을 때, 대기시간을 최소로 하는 시간을 구하는 문제입니다.

 

우리가 해야하는 것은 대기시간을 최소로 하도록 상담원 배치를 하고 나서, 최소 대기 시간을 구해야 합니다.

 

어떻게 하면 최소 대기 시간을 만들도록 상담원을 배치할 수 있을까요?

 

문제 조건에 의해 모든 유형에는 상담원이 한 명씩은 배치되어야 합니다.

우선 한 명씩 상담원을 배치하고,

상담원이 추가되었을 때 가장 많이 대기 시간이 줄어드는 타입에 우선적으로 배치하면 됩니다.

가장 많이 대기시간이 줄어들게 되면

전체에서도 최소로 만들어지는 경우이로 만들어지기 때문에 그리디로 접근할 수 있습니다.

 

문제 접근 순서는 다음과 같습니다.

1. 유형마다 상담 요청 시간 분리
2. 각 유형마다 1~(n-k) 수의 상담사를 배정하고, 상담사 숫자에 따른 각 대기 시간을 구함
3. 우선 각 상담원을 한 명씩 배치
4. 대기시간이 가장 많이 줄어드는 곳에 상담사를 한 명씩 배치 -> 그리디
5. 상담원 배치가 끝나고 계산

 

1. 유형마다 상담 요청 시간 분리

유형이 같아야 겹쳤을 때 대기시간이 존재하게 됩니다.

때문에 유형별로 상담 요청 시간을 분리할 수 있습니다.

for (int[] req : reqs) {
    int startTime = req[0];
    int duration = req[1];
    int type = req[2];

    // 상담 시작 시간과 종료 시간 저장
    timeForEachType.get(type).add(new Time(startTime, startTime + duration));
}

 

2. 각 유형마다 1~(n-k) 수의 상담사를 배정하고, 상담사 숫자에 따른 각 대기 시간을 구함

각 타입마다 상담원을 1에서부터  증가시켜

해당 상담원이 있을 때의 대기시간을 구해 저장합니다.

 

예를 들어, 예제 테스트케이스 1번의 대기시간을 표로 만들면 다음과 같습니다.

 

1번 유형에 상담원이 한 명이면 175분의 대기시간이 걸립니다.

1번 유형에 상담원이 두 명이면 5분의 대기시간이 걸립니다.

1번 유형에 상담원이 세 명이면 0분의 대기시간이 걸립니다.

한 명에서 두 명으로 늘어나면 170분의 대기시간 감소가 발생합니다.

두 명에서 세 명으로 늘어나면 5분의 대기시간 감소가 발생합니다.

 

2번 유형에 상담원이 한 명이면 20분의 대기시간이 걸립니다.

2번 유형에 상담원이 두 명이면 0분의 대기시간이 걸립니다.

한 명에서 두 명으로 늘어나면 20분의 대기시간 감소가 발생합니다.

 

3번 유형에 상담원이 한 명이면 85분의 대기시간이 걸립니다.

3번 유형에 상담원이 두 명이면 0분의 대기시간이 걸립니다.

한 명에서 두 명으로 늘어나면 85분의 대기시간 감소가 발생합니다.

 

즉, 상담원이 n까지 늘어났을 때의 모든 경우의 수를 구해 저장합니다. 이는 아래에서 사용됩니다.

int[][] waitTimeForEachTime = new int[k + 1][n + 1];
for (int type = 1; type < k + 1; type++) { // 유형
    // 해당 타입의 상담을 신청 지원자가 한 명도 없을 때
    if (timeForEachType.get(type).size() == 0) continue;

    // 상담원을 1 부터 배정
    // 각 유형에 한 명은 배치되어야 하므로 n-k+1까지만 계산 가능
    for (int counselors = 1; counselors <= n - k + 1; counselors++) { 
				
    // counselorSize만큼 상담원을 가질 때의 대기시간을 구함
    int waitTime = calculationTime(timeForEachType.get(type), counselors);

    // 현재 상담원 인원으로 상담했을 때 대기시간 저장
    waitTimeForEachTime[type][counselors] = waitTime;
    }
}

 

3. 우선 각 상담원을 한 명씩 배치

문제 조건에 의해 K이하의 모든 유형에는 한 명의 상담원이 배치되어야 합니다.

int[] currentCounselors = new int[k + 1];
for (int type = 1; type < k + 1; type++) {
    currentCounselors[type] = 1;
}

물론, 다른 코드와 통합할 수 있지만 이해를 돕기 위해 따로 뺐습니다.

 

4. 대기시간이 가장 많이 줄어드는 곳에 상담사를 한 명씩 배치

이 부분이 그리디를 적용하는 곳입니다.

 

위 두 번째에서, 유형별로 상담원 인원에 따른 대기시간을 저장했습니다.

 

1번 유형의 대기시간을 가져오면 다음과 같습니다.

기본적으로 한 명이 있고, 한 명일 때 대기시간은 175분입니다.

두 명일때 때 대기시간은 두 명일때 대기시간은 5분입니다.

 

즉, 상담원은 한 명에서 두 명으로 늘어나면 170분의 대기시간 감축이 발생하는 것입니다.

 

다시 표 전부를 가져오겠습니다.

 

현재 유형별 상담원의 수는 다음과 같습니다.

 

모두 상담원이 한 명이고

두 명으로 증가하면 각각 170, 20, 85분의 대기시간 감축이 발생합니다.

 

예제 테스트 케이스의 n = 5이고, k = 3입니다.

유형이 세 개이니 한 명씩 우선 배치하게 되면, 남은 상담원 n은 2가 남습니다.

 

우선 상담원 하나를 가장 대기시간이 많이 줄어드는 유형 1에 배치합니다.

 

 

그러면 이제 상담원 n은 1이 남습니다.

다시 각 상담원이 증가했을 때 최대로 줄어드는 대기 시간을 구합니다.

 

유형 1은 두 명에서 세 명으로 늘어나면 5분이 줄어듭니다.

유형 2는 한 명에서 두 명으로 늘어나면 20분이 줄어듭니다.

유형 3은 한 명에서 두 명으로 늘어나면 85분이 줄어듭니다.

 

상담원을 배치했을 때, 가장 많이 대기시간이 줄어드는 유형 3에 배치합니다.

 

남은 상담원 n이 0으므로 더이상 배치할 수 없습니다.

 

코드까지 넣으면 글이 너무 길어지기 때문에 아래에서 확인하시길 바랍니다.

 

5. 상담원 배치가 끝나고 계산

상담원 배치가 전부 완료되었기 때문에, 배치된 상담원 수에 따라 계산하시면 됩니다.

 

[구현 코드]

import java.util.*;

public class Solution {

    public int solution(int k, int n, int[][] reqs) {
        int answer = 0;

        // 타입마다 시간을 분리할 리스트
        List<List<Time>> timeForEachType = new ArrayList<>();
        for (int i = 0; i < k + 1; i++) {
            timeForEachType.add(new ArrayList<>());
        }

        // 1. 유형마다 시간을 분리
        for (int[] req : reqs) {
            int startTime = req[0];
            int duration = req[1];
            int type = req[2];

            timeForEachType.get(type).add(new Time(startTime, startTime + duration));
        }

        // 2. 각 유형[type]마다 1~(n-k)+1 수의 상담사를 배정하고, 상담사 숫자에 따른 각 대기 시간을 구함
        int[][] waitTimeForEachTime = new int[k + 1][n + 1];
        for (int type = 1; type < k + 1; type++) { // 유형

            // 해당 타입의 상담을 신청 지원자가 한 명도 없을 때
            if (timeForEachType.get(type).size() == 0) continue;

            // 상담원을 1 부터 배정
            for (int counselors = 1; counselors <= (n-k)+1; counselors++) {

                // counselorSize만큼 상담원을 가질 때의 대기시간을 구함
                int waitTime = calculationTime(timeForEachType.get(type), counselors);

                // 현재 상담원 인원으로 상담했을 때 대기시간 저장
                waitTimeForEachTime[type][counselors] = waitTime;
            }
        }

        // 3. 우선 각 상담원을 한 명씩 배치
        int[] currentCounselors = new int[k + 1];
        for (int type = 1; type < k + 1; type++) {
            currentCounselors[type] = 1;
        }

        // 각 유형에 한 명씩 배치하고 남은 상담사 수
        int remainCounselorNumber = n - k;

        // 4. 대기시간이 가장 많이 줄어드는 곳에 상담사를 한 명씩 배치한다. -> 그리디
        while (remainCounselorNumber-- > 0) {
            int maxReduceTime = 0; // 상담사 수가 증가했을 때 대기시간이 가장 많이 줄어드는 시간
            int correspondingType = 0; // 해당 타입의 번호

            for (int type = 1; type < k + 1; type++) {
                // 현재 상담원 수
                int currentCounselorsByType = currentCounselors[type];

                // 현재 상담자수일 때의 대기시간
                int waitingTimeOfCurrentCounselors = waitTimeForEachTime[type][currentCounselorsByType];

                // 상담원이 1 늘었을 때의 대기시간
                int next = waitTimeForEachTime[type][currentCounselorsByType + 1];

                // 상담원이 추가되었을 때 줄어드는 대기시간
                int reduceWaitingTime = Math.abs(waitingTimeOfCurrentCounselors - next);

                // 상담사 인원이 추가 되었을 때, 가장 많이 줄어드는 시간과 유형 저장
                if (reduceWaitingTime >= maxReduceTime) {
                    maxReduceTime = reduceWaitingTime;
                    correspondingType = type;
                }
            }

            // 상담원을 증가시켜도 더 이상 줄어들 대기시간이 없을 때
            if (maxReduceTime == 0) break;

            // 가장 긴 대기시간을 가진 것에 상담원 추가
            currentCounselors[correspondingType]++;
        }

        // 5. 상담원 배치가 끝나고 계산
        for (int type = 1; type < k + 1; type++) {

            // 해당 타입의 상담을 신청 지원자가 한 명도 없을 때 -> 계산할 것이 없음
            if (timeForEachType.get(type).size() == 0) continue;

            int counselors = currentCounselors[type];

			// 상담원당 대기시간은 위에서 구해서 저장했으니 그대로 사용
            answer += waitTimeForEachTime[type][counselors];
        }

        return answer;
    }

    private int calculationTime(List<Time> typeTime, int counselorNumber) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 끝나는 시간 저장
        int waitTime = 0;

        for (Time t : typeTime) { // 해당 타입의 상담 정보들을 가져옴
            if (pq.isEmpty() || pq.size() < counselorNumber) { // 상담원수가 남아 있을 때
                pq.add(t.end);
            } else {
                // 현재 진행중인 상담중 가장 빨리 끝나는 시간
                int earlyConsultEndTime = pq.poll();

                if (t.start < earlyConsultEndTime) { // 대기시간이 있는 경우
                    waitTime += (earlyConsultEndTime - t.start);
                    pq.add(earlyConsultEndTime + (t.end - t.start));
                } else {
                    pq.add(t.end); // 대기시간이 없는 경우 종료시간 저장
                }
            }
        }
        return waitTime;
    }

    private class Time {
        int start, end;

        public Time(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}