[프로그래머스] 상담원 인원 - JAVA 풀이

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

프로그래머스

문제

현대모비스는 우수한 SW 인재 채용을 위해 상시로 채용 설명회를 진행하고 있습니다. 채용 설명회에서는 채용과 관련된 상담을 원하는 참가자에게 멘토와 1:1로 상담할 수 있는 기회를 제공합니다. 채용 설명회에는 멘토 n명이 있으며, 1~k번으로 분류되는 상담 유형이 있습니다. 각 멘토는 k개의 상담 유형 중 하나만 담당할 수 있습니다. 멘토는 자신이 담당하는 유형의 상담만 가능하며, 다른 유형의 상담은 불가능합니다. 멘토는 동시에 참가자 한 명과만 상담 가능하며, 상담 시간은 정확히 참가자가 요청한 시간만큼 걸립니다.
참가자가 상담 요청을 하면 아래와 같은 규칙대로 상담을 진행합니다.
상담을 원하는 참가자가 상담 요청을 했을 때, 참가자의 상담 유형을 담당하는 멘토 중 상담 중이 아닌 멘토와 상담을 시작합니다.만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다립니다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간입니다.모든 멘토는 상담이 끝났을 때 자신의 상담 유형의 상담을 받기 위해 기다리고 있는 참가자가 있으면 즉시 상담을 시작합니다. 이때, 먼저 상담 요청한 참가자가 우선됩니다.
참가자의 상담 요청 정보가 주어질 때, 참가자가 상담을 요청했을 때부터 상담을 시작하기까지 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원을 정하려 합니다. 단, 각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.
예를 들어, 5명의 멘토가 있고 1~3번의 3가지 상담 유형이 있을 때 아래와 같은 참가자의 상담 요청이 있습니다.

---

예시

참가자 8명, 상담유형 3가지, 멘토 5명인 상황

출처 : 프로그래머스

 

멘토를 1번 유형에 2명, 2번 유형에 1명, 3번 유형에 2명 배치하면 대기 시간이 25분으로 최단시간이 됩니다.

 

1번 유형
1번 유형을 담당하는 멘토가 2명 있습니다.
1번 참가자가 상담 요청했을 때, 멘토#1과 10분~70분 동안 상담을 합니다.3번 참가자가 상담 요청했을 때, 멘토#2와 20분~50분 동안 상담을 합니다.5번 참가자가 상담 요청했을 때, 멘토#2와 50분~90분 동안 상담을 합니다.7번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 1번 참가자의 상담이 끝날 때까지 5분 동안 기다리고 멘토#1과 70분~100분 동안 상담을 합니다.

2번 유형
2번 유형을 담당하는 멘토가 1명 있습니다.
6번 참가자가 상담 요청했을 때, 멘토와 60분~90분 동안 상담을 합니다.8번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 6번 참가자의 상담이 끝날 때까지 20분 동안 기다리고 90분~190분 동안 상담을 합니다.

3번 유형
3번 유형을 담당하는 멘토가 2명 있습니다.
2번 참가자가 상담 요청했을 때, 멘토#1과 15분~115분 동안 상담을 합니다.4번 참가자가 상담 요청했을 때, 멘토#2와 30분~80분 동안 상담을 합니다.


상담 유형의 수를 나타내는 정수 k, 멘토의 수를 나타내는 정수 n과 참가자의 상담 요청을 담은 2차원 정수 배열 reqs가 매개변수로 주어집니다. 멘토 인원을 적절히 배정했을 때 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 값의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

출처 : 프로그래머스

---

어떻게 풀 것인가..?

이 문제는 유형별 상담 요청량과 대기 시간을 효율적으로 관리하면서, 제한된 멘토 수를 우선순위 기반으로 그리디하게 분배하는 것이 핵심이다. 각 유형별로 멘토 수를 바꿔가며 사전 계산한 뒤, 가장 대기 시간을 많이 줄일 수 있는 곳에 인원을 할당해 나가는 전략을 통해 최소 대기 시간을 계산할 수 있다.

 

문제가 길다...! 요약을 해봅시다

 

문제 요약

• 현대모비스는 k개의 상담 유형과 n명의 멘토를 보유하고 있다.
• 각 참가자는 [상담 시작 시각, 상담 시간, 상담 유형]으로 상담 요청을 한다.
• 각 멘토는 오직 한 가지 유형만 담당할 수 있으며, 동시에 한 명만 상담 가능하다.
• 참가자는 본인의 상담 유형을 담당하는 멘토 중 비어 있는 멘토가 생길 때까지 기다린다.
• 목표는 전체 참가자의 대기 시간의 합을 최소화하는 것이다.

---

해결 전략

1. 상담 요청을 유형별로 분리

• 입력으로 주어진 상담 요청(reqs)을 상담 유형(type)별로 구분하여 저장한다.
• timelineEachType[type] 리스트에 [start, end] 구조의 Timeline 객체를 저장한다.

List<List<Timeline>> timelineEachType = new ArrayList<>();

 

2. 각 유형별 멘토 수에 따른 대기 시간 계산

• 각 상담 유형마다 상담원을 1명부터 (n - k + 1)명까지 배치했을 때 대기 시간이 어떻게 변하는지 미리 계산해놓는다.
• 이유는 유형별로 적어도 한 명 이상 멘토를 배정해야 하기 때문에, 총 멘토 수는 n - k명만 유동적으로 배분 가능하다.

int[][] waitingEachType = new int[k + 1][n + 1];

 

3. 최소 멘토 배치 후 남은 멘토를 그리디하게 분배

• 각 상담 유형에 상담원 1명을 우선 배치하고, 남은 n - k명을 가장 대기 시간 감소 폭이 큰 유형에 우선 배정한다.
• 그리디 방식으로 감소량이 가장 큰 유형에 멘토를 추가한다. 단, 감소량이 동일하면 번호가 큰 유형이 우선된다 (>= 조건 사용).

if (reduce >= max) { max = reduce; maxType = type; }

 

4. 최종 멘토 배치 결과로 대기 시간 합산

• 각 유형마다 최종 결정된 멘토 수를 기준으로 대기 시간 합을 더해 최종 결과를 도출한다.

answer += waitingEachType[type][consultant];

 

대기 시간 계산 함수 calTime

• 상담원 수(consultant)에 따라 상담 요청을 처리하는 방식은 우선순위 큐를 활용한다.
• 각 멘토의 종료 시간(end)을 PQ에 저장하여, 가장 빨리 끝나는 멘토부터 상담 배정을 시도한다.
• 만약 모든 멘토가 바쁠 경우, 가장 빨리 끝나는 멘토를 기다려야 하므로 대기 시간 += (firstEnd - t.start)를 적용한다.

 

특이사항 및 포인트

• 유형별로 최소 1명의 멘토를 배정해야 하므로 n - k명만 자유롭게 배치 가능하다.
• 상담 요청이 없는 유형은 무시한다.
• Math.abs()를 사용한 이유는 감소량 계산 시 항상 양수로 만들기 위함이지만, 이 경우엔 실제 wait - next로 바꾸는 것이 의미상 더 직관적이다.
• reduce >= max 조건을 쓴 이유는 동일한 감소량일 경우 우선순위가 높은 유형 번호로 선택되게 하기 위함이다.

 

 

전체 코드

import java.util.*;

// k : 상담 유형
// n : 멘토 몇명

// [시작분,걸리는분,유형번호]

class Solution {
    public int solution(int k, int n, int[][] reqs) {
        
        // 유형별로 타임라인을 저장하는 list
        // idx 숫자가 유형 <-- [시작시간,끝나는시간]
        List<List<Timeline>> timelineEachType = new ArrayList<>();

        for (int i = 0; i <= k; i++) { // list에 k개의 유형 만큼 1부터 idx를 만들어준다.
            timelineEachType.add(new ArrayList<>());
        }

        for (int[] req : reqs) { // 유형별로 타임라인을 따로 저장한다.
            int start = req[0];
            int duration = req[1];
            int type = req[2];

            // 해당 유형에 timeline 저장
            timelineEachType.get(type).add(new Timeline(start, start + duration)); // 시작과 끝을 각 유형별로 추가해준다.
        }

        // 각 유형에 1부터 최대 ( 멘토수 (n) - 나빼고 유형수 (k-1)) 상담수를 배치하고 상담자 수에 따른 대기 시간 저장

        int[][] waitingEachType = new int[k + 1][n + 1]; // 유형별 상담원수에 따른 기다림 사람수

        for (int type = 1; type <= k; type++) { // 유형 별
            // 해당 유형에 상담을 신청한 지원자가 없을때
            if (timelineEachType.get(type).isEmpty()) continue; // 해당유형을 원하는 멘토가 없으면 건너뛰기

            // 해당 유형에 몇명의 상담원을 배정할지 최소값부터 최대값까지
            for (int consultant = 1; consultant <= (n - k) + 1; consultant++) {
                // 유형별 idx에서 시작-끝이 저장되어있는 타임라인을 꺼내 calTime을 통해 기다림 시간 측정
                int waiting = calTime(timelineEachType.get(type), consultant);
                // 해당 유형에 현재 상담원 인원으로 상담했을때 기다림수를 저장한다.
                waitingEachType[type][consultant] = waiting;
            }

        }

        // 우선 각 상담원을 한명씩 배치하고 남은 상담수를 구한다. 기다림시간이 많이 줄어드는 곳에 차근차근 상담원 배치
        int[] currCsult = new int[k + 1];
        Arrays.fill(currCsult, 1);

        int remain = n - k; // 상담원 1씩 배치 후 남은 상담원

        while (remain-- > 0) { // 그리디

            int max = 0; // 1 늘었을때 가장 대기시간 많이 줄어드는 시간
            int maxType = 0; // 그 유형 번호

            for (int type = 1; type <= k; type++) {
                // 현재 상담원 수
                int curr = currCsult[type];
                // 현재 상담원 수에서의 기다림 시간
                int wait = waitingEachType[type][curr];
                // 상담원이 1 늘었을때 기다림 시간
                int next = waitingEachType[type][curr + 1];
                // 상담원이 추가되었을 때 줄어드는 대기시간
                int reduce = Math.abs(wait - next); // 왜 abs일까?

                // 상담원 추가되었을때 가장 많이 줄어드는 시간과 유형 저장
                if (reduce >= max) { // 왜 초과가 아닐까?
                    max = reduce;
                    maxType = type;
                }
            }

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

            // 가장 긴 대기시간을 가진 것에 상담원 추가
            currCsult[maxType]++;
        } // 그리디 끝

        int answer = 0;

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

            // 타임 라인이 없으면 패스
            if (timelineEachType.get(type).isEmpty()) continue;

            // 정해진 상담원 수 불러오기
            int consultant = currCsult[type];

            // 답에 더한다 각 타입의 최상의 기다림 시간을
            answer+=waitingEachType[type][consultant];

        }
        return answer;

    } // main 끝

    static int calTime(List<Timeline> timelines, int consultant) { // 상담원 수 몇명 배치?
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 우선 순위 큐
        int waiting = 0; // 기다린 시간

        for (Timeline t : timelines) { //
            if (pq.isEmpty() || pq.size() < consultant) {
                pq.offer(t.end);
            } else {
                int firstEnd = pq.poll();

                if (t.start < firstEnd) {
                    waiting += firstEnd - t.start;
                    pq.offer(firstEnd + (t.end - t.start));

                } else {
                    pq.add(t.end);
                }
            }
        }
        return waiting;
    }

    static class Timeline {
        int start, end;

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