[프로그래머스] 214288 상담원 인원 (JavaScript)

문제

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

풀이

여느 때와 마찬가지로 문제를 읽고 제한사항부터 확인했다.

각 유형에 멘토를 한 명씩 먼저 배정한 뒤, 남은 멘토를 분배하는 조합의 수는 $\binom{n - 1}{k - 1}$ 이다. 각 멘토 배정 조합에 대해 모든 요청을 처리한다고 생각하면, 조합의 수는 최대 $\binom{19}{4} = 3,\!876$ 개다. reqs는 최대 $200$ 개 이므로 총 연산은 최대 $775,\!200$ 로 완전 탐색으로도 충분히 풀이할 수 있다고 판단했다.

그래서 이후에는 구현에 집중하기로 했다.

구현 카테고리의 문제를 풀 때는 상상력을 동원해 실제로 동작하는 흐름을 그대로 코드로 옮기는 편이다. 처음에는 멘토의 입장보다 참가자의 입장이 조금 더 익숙해서, reqs에 들어 있는 참가자의 관점으로 코드를 구현했다.

상담실에서는 멘토들이 참가자의 상담을 처리하고, 새로운 참가자는 대기실에서 기다리는 그림을 머릿속에 그리며 queue를 구현했다. 그리고 참가자의 상담이 시작될 때까지 기다린 시간을 구하는 식으로 접근했다. 그런데 이 방식은 새로운 참가자가 대기실에 들어올 때마다 확인해야 할 경우가 많았다. 기다리던 참가자가 상담실로 이동할 수도 있고 아닐 수도 있으며, 새로 도착한 참가자가 대기실에 들어가지 않고 바로 상담을 시작할 수도 있었다. 생각해야 할 분기가 꽤 많았다.

이후 관점을 바꿔 멘토의 입장에서 생각했다. 각 멘토가 다시 상담할 수 있는 시각을 우선순위 큐에 저장해 두면, 참가자의 요청이 들어올 때 가장 빨리 상담을 끝내는 멘토를 바로 찾을 수 있다. 참가자의 대기열을 직접 관리하는 대신 멘토들의 상담 가능 시각을 관리하니 훨씬 단순하게 처리할 수 있었다.

JavaScript의 배열 복사 이슈를 또 간과했다. 멘토 배정 조합을 저장할 때 counts를 그대로 넣으면 모든 조합이 같은 배열을 참조하게 된다. 따라서 현재 상태를 복사한 [...counts]를 저장해야 한다. counts 때문에 디버깅하느라 애먹었다. 유의하자.

소스 코드

javascript

class PriorityQueue {
    constructor(values = []) {
        this.heap = [];

        for (const value of values) {
            this.push(value);
        }
    }

    push(value) {
        this.heap.push(value);
        this.#bubbleUp();
    }

    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const root = this.heap[0];
        const last = this.heap.pop();

        this.heap[0] = last;
        this.#bubbleDown();

        return root;
    }

    #bubbleUp() {
        let current = this.heap.length - 1;

        while (0 < current) {
            const parent = Math.floor((current - 1) / 2);

            if (this.heap[parent] <= this.heap[current]) break;

            [this.heap[parent], this.heap[current]] = [
                this.heap[current],
                this.heap[parent],
            ];

            current = parent;
        }
    }

    #bubbleDown() {
        let current = 0;

        while (true) {
            const left = current * 2 + 1;
            const right = left + 1;
            let smallest = current;

            if (
                left < this.heap.length &&
                this.heap[left] < this.heap[smallest]
            ) {
                smallest = left;
            }

            if (
                right < this.heap.length &&
                this.heap[right] < this.heap[smallest]
            ) {
                smallest = right;
            }

            if (smallest === current) break;

            [this.heap[current], this.heap[smallest]] = [
                this.heap[smallest],
                this.heap[current],
            ];

            current = smallest;
        }
    }
}

const evaluate = (rooms, requests) => {
    let waitingTime = 0;

    for (const [requestedAt, duration, type] of requests) {
        const mentors = rooms[type - 1];
        const availableAt = mentors.pop();
        const startedAt = Math.max(requestedAt, availableAt);

        waitingTime += startedAt - requestedAt;
        mentors.push(startedAt + duration);
    }

    return waitingTime;
};

const buildMentorCounts = (k, n) => {
    const combinations = [];
    const counts = Array(k).fill(1);

    const dfs = (type, remaining) => {
        if (type === k - 1) {
            counts[type] += remaining;
            combinations.push([...counts]);
            counts[type] -= remaining;

            return;
        }

        for (let count = 0; count <= remaining; count++) {
            counts[type] += count;
            dfs(type + 1, remaining - count);
            counts[type] -= count;
        }
    };

    dfs(0, n - k);

    return combinations;
};

const createRooms = (counts) =>
    counts.map(count =>
        new PriorityQueue(Array(count).fill(0))
    );

const solution = (k, n, reqs) =>
    buildMentorCounts(k, n).reduce(
        (answer, counts) => Math.min(answer, evaluate(createRooms(counts), reqs)),
        Infinity
    );

[프로그래머스] 214288 상담원 인원 (JavaScript)

문제

풀이

소스 코드

Share this post