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

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

세번째 풀이

• 각 상담유형을 배열로 만들고 필요한 상담원의 수를 넣어놓는 방법이다.
• 여기서 하나 상담유형의 상담시간의 최대범위는 1100이고
• 5개 유형을 20명이 나눈다고 했을때 경우의 수가 3003임으로
  - 55003003 = 16.5 10^5 으로 완전탐색 할만하다 판단.
• 먼저 각 배열을 만들고 경우의 수에 따라 대기시간을 계산해보자.

실패한 코드

• 5번 틀리고 10번부터 20번까지 틀림
• 예시도 틀림.

import java.util.*;
class Solution {
    int minTime = Integer.MAX_VALUE;
    HashMap<Integer, int[]> map = new HashMap<>();

    public int solution(int k, int n, int[][] reqs) {
        // 상담유형 테이블 만들기,
        for(int i = 1; i <= k; i++) {
            int[] arr= new int[1100];
            map.put(i, arr);
        }

        // reqs를 순회하면서 상담유형 테이블에 인원을 기록한다.
        for(int[] req : reqs) {
            int start = req[0];
            int end = req[1]+start;
            int type = req[2];
            for(int i = start; i < end; i++) { // 끝나는 시간엔 다른 상담원을 받을 수 있으니 빼주자
                map.get(type)[i]++;
            }
        }
        // 상담원수 n이 상담유형에 배치될 수 있는 방법을 구한다.

        combi(k,  n - k , new int[k+1]);
        return minTime;
    }
    private void combi(int k, int n, int[] mentorList){
        if(n == 0){ //더이상 배분할 멘토수가 없다면
            minTime = Math.min( minTime, getTotalTime(mentorList));
            // 로직 수행
            return;
        }
        for(int i = 1; i<=k; i++){
            mentorList[i]++;
            combi(k, n-1 , mentorList);
            mentorList[i]--;
        }
    }
    // 상담원리스트을 받아서, 모든 유형의 대기시간을 구한다.
    private int getTotalTime(int[] mentorList) {
        int totalTime = 0;
        for(int i = 1; i < mentorList.length; i++) {
            int waitTime = getWaitTime(mentorList[i] + 1, map.get(i));
            totalTime += waitTime;
        }
        return totalTime;

    }

    // 상담원수랑 상담유형 필요인원테이블을 비교하여, 상담원 수보다 작을 경우 대기시간을 올린다.
    private int getWaitTime(int mentorNum,int[] table) {
        int waitTime = 0;
        for(int n : table) {
            if( n > mentorNum) {
                waitTime++;
            }
        }
        return waitTime;
    }
}

원인 분석

• 먼저 상담 요청한 참가자가 우선시 되는 이슈로 인해, 미리 값을 정해놓기에는 오차가 생긴다.
• 지난 번 풀었던 방식이 오히려 더 맞는 방법인것 같다.
  
• 일단 먼저 시간초과나는 이유는 Stackoverflow라서, 경우의 수 구하는 조합 로직과 대기시간 구하는 로직을 분리하였다.

산넘어 산

• 하지만 그럼에도 아래처럼 메모리초과가 났고,그원인은 조합 로직에 있는 것 같다.

문제 해결

• 너무 크게 돌아왔다. 백트래킹로직에서 index 실수를 한 것이 원인이였다.

	//k 인자값도 0으로 들어옴
	private void combi(int k, int n, int[] mentorList){
        if(n == 0){
            // 로직 수행
            minTime = Math.min(minTime, getWatingTime(mentorList.clone()));
            return;
        }
        for(int i = k; i< mentorList.length; i++){
            mentorList[i]++;
            // 기존 코드 combi(k, n-1 , mentorList);

            combi(i, n - 1 , mentorList);
            mentorList[i]--;
        }
    }
   

• 이렇게 인덱스를 활용하면서 백트래킹을 했어야했는데 그렇지 못한것이 실수였다.
• 코테를 꾸준히 해야 감을 유지할 수 있을 것 같다.

성공한 코드

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

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

    private int getWatingTime(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;
    }

}