[node.js] 스타트와 링크 ( 백준 14889번 )

// 백준 14889번 스타트와 링크를 풀었습니다.
// 조합을 사용하여 풀었습니다.

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const combinations = function* (elements, selectNumber) {
    for (let i = 0; i < elements.length; i++) {
        if (selectNumber === 1) {
            yield [elements[i]];
        } else {
            const fixed = elements[i];
            const rest = elements.slice(i + 1);
            for (const a of combinations(rest, selectNumber - 1)) {
                yield [fixed, ...a];
            }
        }
    }
};

const getAblilty = (team, map) => {
    let sum = 0;
    for (let i = 0; i < team.length; i++) {
        const from = team[i];

        for (let j = 0; j < team.length; j++) {
            const to = team[j];
            sum += map[from][to];
        }
    }
    return sum;
};

const input = [];
rl.on("line", (line) => {
    input.push(line);
}).on("close", () => {
    const num = Number(input.splice(0, 1));
    const map = [...input].map((el) => el.split(" ").map(Number));
    const people = new Array(num).fill(0).map((el, i) => i);

    let minValue = 987654321;
    for (const a of combinations(people, num / 2)) {
        const start = a;
        const link = [...people].filter((el) => !start.includes(el));

        const startAbility = getAblilty(start, map);
        const linkAbility = getAblilty(link, map);

        const difference = Math.abs(startAbility - linkAbility);
        minValue = Math.min(minValue, difference);
    }
    console.log(minValue);
});

조합을 사용하여 한 쪽 집단을 구하고, 나머지 한 쪽 집단을 구한 후, 각각 점수를 구해서 차이를 비교해주면 된다.
answer 라는 배열을 만들어 최솟값들을 저장한 다음, Math.min(...answer) 형태로 구하고자 했는데
콜 스택 초과가 떴다.
경우의 수가 배열의 크기보다 크기 때문에 발생한 일이다.

콜 스택이라고 하면 함수의 재귀가 터진 것처럼 보이는데, 실제로는 배열이라서 볼 때마다 헷갈리곤 한다.
앞으로는 그 때 그 때 최솟값을 구해서 저장해둬야 겠다.