[프로그래머스] 시험장 나누기 (Javascript, 2021 카카오 채용연계형 인턴십)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/81305

코딩테스트 연습 - 시험장 나누기

 

풀이

자바스크립트로 풀었는데 큰 문제가 있었습니다. 제출 시 몇몇 효율성 테케에서 의문의 런타임 에러를 뱉더라구요.

최대 범위 테스트 케이스를 따로 만들어 로컬에서 돌려보니 다음 에러가 원인이었습니다.

RangeError: Maximum call stack size exceeded

그래프 최대 깊이가 1만 정도 되는데, 이를 재귀 함수로 구현하다 보니 콜 스택이 터져나가 버리는 상황이었습니다. 파이썬은 스택 크기 조절이 되는데 왜 JS는... ㅜㅜ

꼬리 재귀 최적화를 시도해봤지만 포스트 오더로 구현한지라 리턴 값을 가지고 연산을 해야 하기 때문에 먹히질 않아서 그냥 깡 스택 반복문으로 유사 재귀 함수를 구현해서 해결했습니다. 진짜 슬프네요 이건..

 

---

문제를 더 간단하게 만들기

이진트리가 주어지고, $k$개의 그룹으로 나눴을 때 각 그룹 인원수 중 최댓값이 최소가 되는 값을 구해야 합니다.

효율성을 생각하면 풀이가 감도 안오죠? 좀 다르게 생각해봅시다.

 

만약 인원 최댓값이 주어지고(= 고정시킨다), 이 최댓값을 넘기지 않고 적절히 그룹을 만들었을 때 최적의 그룹 수를 구할 수 있다고 합시다.

그럼 가능한 모든 최댓값을 대입해서 그룹의 수가 $k$이하가 되는 값 중 가장 작은 값을 정답으로 취하면 됩니다.

이런 방식을 조금 어려운 말로 "최적화 문제를 결정 문제로 바꾼다"라고 합니다.

 

결정 문제로 바꿔도 아직 문제가 남아있습니다. 확인해봐야 할 유효한 인원 최댓값의 범위가 너무 큽니다.

가능한 범위의 최소는 트리의 정점 중 가장 큰 가중치 값이고, 최대로는 모든 정점의 가중치 합이 될 수 있습니다.

최소 1부터 최대 100,000,000 까지인데 1억개의 후보를 다 확인하기엔 시간이 너무 오래 걸립니다. 최적 그룹 수를 구하는데도 시간이 드니까요.

 

이를 해결하기 위해 이분 탐색을 이용할 수 있습니다. 이분 탐색을 사용하면 $O(\log_{2}{10^8})$ 정도의 복잡도로 후보를 쳐낼 수 있습니다.

 

최적 그룹 수 구하기

최댓값(limit)을 고정한 상태에서 최적 그룹의 수는 다음처럼 구할 수 있습니다.

 

1) 포스트 오더로 트리를 순회합니다.

2) 각 순회의 리턴 값은 { [아래에서부터 그룹을 지어왔을 때, 현재까지의 코스트 합], [현재까지의 최적 그룹 수] }입니다.

3) 왼쪽, 오른쪽 자식의 정보를 바탕으로 현재 정점을 어떻게 그룹 지을지 결정합시다.

  3-1) 만약 두 자식과 현재 정점의 코스트 합이 limit 이하라면, 현재 정점도 그룹에 포함시키면 됩니다.

  3-2) 만약 한쪽 자식이랑만 그룹을 지을 수 있다면, 추가되는 그룹의 수는 같으니 코스트가 더 적은 쪽과 그룹 지으면 됩니다. 추가되는 그룹 수는 1입니다.

  3-3) 어떤 자식과도 그룹 지을 수 없다면, 자식들과 그룹지을 수 없으니 그룹의 수를 2 올려줍니다.

4) 루트 정점의 그룹수를 반환하여 판단해줍시다.

 

DP라고 의식해서 풀진 않았는데 풀이를 쓰고 보니 그냥 DP였네요. 리턴 값을 dp 배열의 값이라고 생각하시면 되겠습니다.

 

 

 

정답 코드

function solution(k, num, links) {
    const tree = links.reduce((tree, v, i) => {
        tree[i] = {
            cost: num[i],
            l: v[0],
            r: v[1],
        };
        return tree;
    }, {});

    const n = num.length;
    const root = links.reduce((root, v) => {
        const [a, b] = v;
        if (a > 0) root -= a;
        if (b > 0) root -= b;
        return root;
    }, n * (n - 1) / 2);

    const go = limit => {
        const callStack = [root];
        const returnValues = {
            "-1": {
                cost: 0,
                cnt: 0,
            }
        };
        callStack.back = function () { return this[this.length - 1];};
        while (callStack.length) {
            const now = callStack.back()
                , {cost, l, r} = tree[now]
                , lRes = returnValues[l]
                , rRes = returnValues[r];

            if (!lRes) {
                callStack.push(l);
                continue;
            }
            if (!rRes) {
                callStack.push(r);
                continue;
            }
            callStack.pop();

            returnValues[now] = {
                cost,
                cnt: returnValues[l].cnt + returnValues[r].cnt,
            }
            const ret = returnValues[now];

            const underLimit = (...nodes) => {
                const sum = nodes.reduce((sum, v) => sum += v.cost, 0);
                return sum <= limit;
            }

            if (underLimit(ret, lRes, rRes)) {
                ret.cost += lRes.cost + rRes.cost;
            } else if (underLimit(ret, lRes) || underLimit(ret, rRes)) {
                ret.cost += Math.min(lRes.cost, rRes.cost);
                ret.cnt += 1;
            } else {
                ret.cnt += 2;
            }
        }
        return returnValues[root];
    };

    const getAnswer = () => {
        let l = Math.max(...num), r = 11111 * n;
        let ans = r;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);

            if (go(m).cnt <= k - 1) {
                r = m - 1;
                ans = Math.min(ans, m);
            } else {
                l = m + 1;
            }
        }
        return ans;
    };

    return getAnswer();
}