[코딩테스트 연습]상담원 인원

🔍 난이도 : Lv.3
🔤 언어 : java
📎 문제 링크 : 상담원 인원

첫 풀이

• 여분 멘토를 잘 사용하면 될 것 같아, 멘토을 담아주는 자료구조와 상담시간을 담아두는 자료구조를 생각하다보니,
• HashMap과 우선순위 큐를 생각했다.

실패한 코드(결과 40.0점)

• 5번 틀리고 10번부터 20번까지 틀림
• 단, 시간초과는 나지 않음

import java.util.*;
class Solution {
    public int solution(int k, int n, int[][] reqs) {
        // 멘토를 각 상담유형별로 한명씩 배치한다. 
        // 현재 시간을 젠다. 
        // 현재 시간에 가능한 멘토들을 체크한다.
            // 각 멘토들은 현재 진행중인 상담시간을 적는다. 
        // 기다려야한다면 최소시간을 계산한다. 
        
        
        HashMap<Integer, PriorityQueue<Integer>> consultingNumMap = new HashMap<>();
        for(int i = 1; i<= k; i++){
            PriorityQueue<Integer> mentorQueue = new PriorityQueue<>();
            mentorQueue.add(0);
            consultingNumMap.put(i, mentorQueue);
        }
        // 여분 멘토 
        int remainMentor = n - k;   
        
        int[] mentorTime = new int[n + 1];
        int curTime = 0;
        int waiting = 0;
        //상담 시작
        for(int[] req : reqs){
            curTime = req[0];
            int consultingTime = consultingNumMap.get(req[2]).peek(); // 멘토 리스트 , 멘토리스트 대신 우선순위 큐로 대체
            if(curTime < consultingTime){
                // 여분 멘토을 바로 배정해주는건 좋지않음. 
                if(remainMentor > 0){
                    consultingNumMap.get(req[2]).add(curTime+ req[1]);
                    remainMentor--;
                }
                // 대기
                else{
                    waiting += (consultingTime - curTime);
                    consultingNumMap.get(req[2]).poll();
                    consultingNumMap.get(req[2]).add(consultingTime + req[1]);
                }
            }
            // 상담이 마쳤다면 
            else{
                 consultingNumMap.get(req[2]).poll();
                 consultingNumMap.get(req[2]).add(curTime+ req[1]);
            }
        }
        return waiting;
    }
}

원인 분석

• 여분 멘토를 필요할 때 바로 지정해줬기 때문에, 대기시간을 최소로 만들지는 못한다.
• 그것을 확인하기 위해서는 최적의 방법을 찾아야하기때문에 고민이 필요하다.

두번째 풀이

• 상담유형의 갯수가 최대 5개, 멘토는 최대 20명, 게다가 상담유형 한곳에는 꼭 한명은 있어야함으로 올 수 있는 경우의 수는 C(15, 5) = 15! / (5! * (15 - 5)!) = 3003
• 충분히 완전 탐색을 해볼만한 수 이다.

실패한 코드(40.0점)

• 최소의 상담시간 결과가 나오긴하지만, 이번에는 9번부터 20번까지 시간초과가 난다.

import java.util.*;
class Solution {
    int minTime = Integer.MAX_VALUE;
    int[][] greqs = null;
    public int solution(int k, int n, int[][] reqs) {
        // 여분 멘토
        int remainMentor = n - k;
        int[] mentorList = new int[k];
        greqs = reqs;
        combi(k,remainMentor, mentorList);
        return minTime;

    }
    private void combi(int k, int n, int[] mentorList){
        if(n == 0){
            // 로직 수행
            minTime = Math.min(minTime, getWatingTime(k, mentorList.clone()));
            return;
        }
        for(int i = 0; i<k; i++){
            mentorList[i]++;
            combi(k, n-1 , mentorList);
            mentorList[i]--;
        }
    }

    private int getWatingTime(int k ,int[] mentorList){
        // 우선순위 큐로 넣되, 멘토리스트를 참고하여 넣자
        HashMap<Integer, PriorityQueue<Integer>> consultingNumMap = new HashMap<>();
        for(int i = 1; i<= k; i++){
            PriorityQueue<Integer> mentorQueue = new PriorityQueue<>();
            while(mentorList[i-1]> -1){
                mentorQueue.add(0);
                mentorList[i-1]--;
            }
            consultingNumMap.put(i, mentorQueue);
        }

        int curTime = 0;
        int waiting = 0;
        //상담 시작
        for(int[] req : greqs){
            curTime = req[0];
            int consultingTime = consultingNumMap.get(req[2]).peek();
            // 멘토 리스트 , 멘토리스트 대신 우선순위 큐로 대체
            if(curTime < consultingTime){
                // 대기
                waiting += (consultingTime - curTime);
                consultingNumMap.get(req[2]).poll();
                consultingNumMap.get(req[2]).add(consultingTime + req[1]);
            }
            // 상담이 마쳤다면
            else{
                consultingNumMap.get(req[2]).poll();
                consultingNumMap.get(req[2]).add(curTime+ req[1]);
            }
        }
        return waiting;
    }

}

원인 분석

• 완전탐색에 대한 부담이 큰것 같다.
• 먼가 성능면으로 리펙토링을 하면 해결되지 않을까 한다. 다음에는 리펙토링을 해보자