프로그래머스 [Lv. 3] 상담원 인원 {언어 : JavaScript}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/214288?language=javascript

프로그래머스

정답 코드

// 멘토 n명, 1~k번 상담 유형, 각 멘토는 k개의 상담 유형 중 하나만 담당
function solution(k, n, reqs) {
    // 단, 각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.
    let answer = 1000 * 3000;
    
    const types = Array.from({length: n+1}, () => []);
    reqs.forEach(([a, b, c]) => {
        types[c].push([a, b, a+b]);
    })
    const lens = types.map((e) => e.length);
    const checkTime = (s, i) => {
        const lenR = lens[s];
        // 기다리는 시간 없음
        if (lenR <= i) {
            return 0;
        }
        let time = 0;
        const mentos = Array.from({length: i}, (_, j) => types[s][j][2]);
        for (let l = i; l < lenR; l++) {
            let endT = 300000000;
            let nextI = 0;
            for (let m = 0; m < i; m++) {
                if (endT > mentos[m]) {
                    endT = mentos[m];
                    nextI = m;
                }
            }
            // 계산
            const [a, b, c] = types[s][l];
            // 시작 시간 보다 초과된 경우
            if (a < endT) {
                mentos[nextI] += b;
                time += (endT - a);
            } else {
                mentos[nextI] = c;
            }
        }
        return time;
    }
    
    const dfs = (s, cnt, t) => {
        // 가지치기
        if (answer <= t) {
            return;
        }
        if (s === k) {
            const lastTime = t + checkTime(s, cnt);
            if (lastTime < answer) {
                answer = lastTime;
            }
            return;
        }
        for (let i = 1; i < cnt; i++) {
            dfs(s+1, cnt-i, t+checkTime(s, i));
        }
    }
    dfs(1, n, 0);
    return answer;
}

풀이 방법

1. n명을 k유형에 각각 1명 이상씩 분배하는 조합을 만든다.
2. 조합을 만들면 바로 시간을 계산한다.
   1. 조합은 dfs를 이용한다.
   2. 일단 1보다 크고 cnt보다 작은 수 중에 하나를 재귀로 넘긴다.
   3. 넘기는 과정에서 i값, 즉 현재의 멘토 수와 현재 상담 유형 s를 가지고 시간을 구해서 더해준다.
   4. 마지막으로 s가 k에 도달하면 남은 cnt는 전부 상담 유형 s에 멘토로 투입되므로 위와 동일하게 시간을 구해서 더해준다.
   5. 마지막으로 구한 값을 answer와 비교해서 작으면 answer에 넣으면서 최소 시간을 갱신한다.
3. 현재 시간이 answer 보다 크거나 같은 경우는 재귀를 이어갈 필요가 없으므로 중단한다.
4. answer를 반환하면 끝!

느낀점

• 최소 시간을 적당히 큰 수로 했는데 이 부분이 틀렸었다.
• 다시 보면 좋은 문제인 이유가 사실 조합을 만드는데 너무 큰 시간이 들 것 같아서 못 풀었다.
• 하지만 그냥 조합 만들고 계산하는 문제라는 것을 알고 dfs와 백트래킹 활용해서 풀었다.
• 재귀의 깊이가 k까지이기 때문에 재귀 깊이는 고려하지 않았다.
• 거듭 말하지만 JavaScript의 재귀 깊이가 10000 ~ 20000인 점을 고려하여 안전하게 9000이상이면 stack을 활용한 재귀를 사용하자.