[JAVA] 프로그래머스 level3 상담원 인원

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

프로그래머스

코딩테스트 연습 > 2023 현대모비스 알고리즘 경진대회 예선 > 상담원 인원 

 

문제 접근 

시뮬레이션/구현 문제

 

1. 유형에 따라 큐에 데이터 넣기 

2. 유형에 따라 1 ~ MAX 멘토수에 대기 시간 계산 

3. 백트래킹을 통한 조합 만들기

4. MIN 찾기 

 

1) 유형에 따라 큐에 데이터 넣기 

static Queue<int[]>[] q;

q = new LinkedList[k+1];

// 큐 초기화 
for(int i = 0; i <= k; i++){
    q[i] = new LinkedList<>();
}
for(int i = 0; i < reqs.length; i++){
    q[reqs[i][2]].add(new int[]{reqs[i][0], reqs[i][1]});
}

 

2) 유형에 따라 1 ~ MAX 멘토수에 대기 시간 계산, 기록 

 

모든 상담 유형에는 최소 1명의 멘토가 있어야 한다. -> MAX: n(총 멘토 숫자) - k(문제 유형) + 1; 

 

EX) MEMO[1][3]: 문제유형1 멘토수 3명 이면 필요한 대기 시간  

memo = new int [k+1][max+1];
for(int i = 1; i <= k; i++){
    for(int j = 1; j <= max; j++){
        memo[i][j] = func(i, j);
    }
}

// x = 유형 y = 멘토 숫자 
public static int func(int x, int y){
    int size = q[x].size();
    if(size == 0) return 0;

    int latency = 0; // 시간
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int i = 0; i < y; i++){
        pq.add(0);
    }

    for(int i = 0; i < size; i++){
        int [] cur = q[x].poll();

        if(cur[0] >= pq.peek()){
            pq.poll();
            pq.add(cur[0] + cur[1]);
        }
        else{
            latency += pq.peek() - cur[0];
            pq.add(pq.poll() + cur[1]);
        }
        q[x].add(cur);
    } 
    return latency;
}

 

3,4) 백트래킹을 통한 조합 만들기 + MIN 찾기 

 

EX) 유형이 3개 멘토 5명 

{1,1,3}

{1,2,2}

{2,1,2}

.... 

 

이미 기록해둔 메모에서 꺼내서 합의 최솟값 찾기

static List<List<Integer>> list = new ArrayList<>();
 
find(max);   
 
public static void find(int max){
    comb(new ArrayList<>(), max, 0);

    for(List<Integer> temp : list){
        int sum = 0;
        for(int i = 1; i <= K; i++){
            sum += memo[i][temp.get(i-1)];
        }
        if(min > sum){
            min = sum;
        }
    }
}
public static void comb(ArrayList<Integer> temp, int max, int sum){
    if(temp.size() == K){
        if(sum == N){
            list.add(temp);
        }
        return;
    }
    for(int i = 1; i <= max; i++){
        ArrayList<Integer> next = new ArrayList<>(temp);
        next.add(i);
        comb(next, max, sum + i);
    }
}

 

개인적으로 아쉬운 부분 ArrayList 대신 Array를 사용하고 매개변수로 depth를 넘겨주고 Array[depth++] 조건에 맞으면 바로 검사하는 방식이 시간 복잡도 측면에서나 코드 가독성도 더 좋았을듯하다. 

최종 코드

import java.util.*;

class Solution {
    static Queue<int[]>[] q;
    static int [][] memo;
    static int min = 10000000;
    static int K, N;
    static List<List<Integer>> list = new ArrayList<>();
    public int solution(int k, int n, int[][] reqs) {
        
        int max = n - k + 1; 
        K = k;
        N = n;
        
        q = new LinkedList[k+1];
        for(int i = 0; i <= k; i++){
            q[i] = new LinkedList<>();
        }
        for(int i = 0; i < reqs.length; i++){
            q[reqs[i][2]].add(new int[]{reqs[i][0], reqs[i][1]});
        }
        
        memo = new int [k+1][max+1];
        for(int i = 1; i <= k; i++){
            for(int j = 1; j <= max; j++){
                memo[i][j] = func(i, j);
            }
        }
        
        find(max);      
        return min;
    }
    public static void find(int max){
        comb(new ArrayList<>(), max, 0);
        
        for(List<Integer> temp : list){
            int sum = 0;
            for(int i = 1; i <= K; i++){
                sum += memo[i][temp.get(i-1)];
            }
            if(min > sum){
                min = sum;
            }
        }
        
    }
    public static void comb(ArrayList<Integer> temp, int max, int sum){
        if(temp.size() == K){
            if(sum == N){
                list.add(temp);
            }
            return;
        }
        for(int i = 1; i <= max; i++){
            ArrayList<Integer> next = new ArrayList<>(temp);
            next.add(i);
            comb(next, max, sum + i);
        }
    }
        
    // x = 유형 y = 멘토 숫자 
    public static int func(int x, int y){
        int size = q[x].size();
        if(size == 0) return 0;
        
        int latency = 0; // 시간
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < y; i++){
            pq.add(0);
        }
        
        for(int i = 0; i < size; i++){
            int [] cur = q[x].poll();
            
            if(cur[0] >= pq.peek()){
                pq.poll();
                pq.add(cur[0] + cur[1]);
            }
            else{
                latency += pq.peek() - cur[0];
                pq.add(pq.poll() + cur[1]);
            }
            q[x].add(cur);
        } 
        return latency;
    }
}

 

감사합니다