[programmers/js]주사위 고르기

주사위 고르기

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

문제 설명

N개의 주사위가 주어집니다. 각 주사위는 6개의 면을 가지고 있고, 면마다 정수가 적혀 있습니다.
이 중 N/2개의 주사위를 A가 고르고, 나머지 N/2개는 B가 갖습니다.

A와 B는 각각 자신이 고른 주사위를 동시에 던져, 나온 숫자의 합이 더 큰 쪽이 승리합니다.

A가 이길 확률이 가장 높은 조합을 구하고, 그때 A가 고른 주사위의 인덱스를 반환해야 합니다.
(여러 개일 경우, 사전순으로 가장 빠른 조합)

풀이

1. 조합 만들기
   총 주사위 n개에서 A가 사용할 주사위 2/N 조합을 구합니다.

const getCombinations = (arr, select) => {
    if (select === 0) return [[]];
    if (arr.length < select) return [];
    const [first, ...rest] = arr;
    const pick = getCombinations(rest, select - 1).map(v => [first, ...v]);
    const notPick = getCombinations(rest, select);
    return [...pick, ...notPick];
};

2. 각 조합에서 나올 수 있는 주사위 합을 모두 구합니다.
   누적합 방식을 적용해 각 배열을 돌면서 값을 더해줍니다.

const getSums = (dices) => {
    let result = [0];
    for (const dice of dices) {
        const temp = [];
        for (const sum of result) {
            for (const face of dice) {
                temp.push(sum + face);
            }
        }
        result = temp;
    }
    return result;
};

3. A의 승리 횟수를 계산합니다.
   각 값을 모두 비교하면 시간초과가 발생합니다.
   값을 정렬 후 이분 탐색을 사용해 A의 승리 횟수를 구해줍니다.

const getWinCount = (aSums, bSums) => {
    let count = 0;
    bSums.sort((a, b) => a - b);
    for (const a of aSums) {
        let left = 0, right = bSums.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (bSums[mid] < a) left = mid + 1;
            else right = mid;
        }
        count += left; // a가 이긴 경우의 수
    }
    return count;
};

4. 전체 코드

const getCombinations = (arr, select) => {
    if (select === 0) return [[]];
    if (arr.length < select) return [];
    const [first, ...rest] = arr;
    const pick = getCombinations(rest, select - 1).map(v => [first, ...v]);
    const notPick = getCombinations(rest, select);
    return [...pick, ...notPick];
};


const getSums = (dices) => {
    let result = [0];
    for (const dice of dices) {
        const temp = [];
        for (const sum of result) {
            for (const face of dice) {
                temp.push(sum + face);
            }
        }
        result = temp;
    }
    return result;
};


const getWinCount = (aSums, bSums) => {
    let count = 0;
    bSums.sort((a, b) => a - b);
    for (const a of aSums) {
        let left = 0, right = bSums.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (bSums[mid] < a) left = mid + 1;
            else right = mid;
        }
        count += left; // a가 이긴 경우의 수
    }
    return count;
};


function solution(dice) {
    const N = dice.length;
    const diceIndices = Array.from({ length: N }, (_, i) => i);
    const combinations = getCombinations(diceIndices, N / 2);

    let maxWin = -1;
    let answer = [];

    for (const comb of combinations) {
        const rest = diceIndices.filter(i => !comb.includes(i));
        const aDices = comb.map(i => dice[i]);
        const bDices = rest.map(i => dice[i]);

        const aSums = getSums(aDices);
        const bSums = getSums(bDices);
        const winCount = getWinCount(aSums, bSums);

        if (winCount > maxWin) {
            maxWin = winCount;
            answer = comb;
        }
    }

    return answer.map(i => i + 1);
}