Portfolio

1️⃣ 문제

2️⃣ 문제 해결 전략

주사위 번호 조합 구하기(A팀만) ⇒ dfs

주사위 번호마다 나올 수 있는 합 배열 구하기(A,B 팀 모두)

주사위 조합마다 A합>B합 개수 구하기 ⇒ 이진탐색

3 중에 제일 큰 값의 주사위 번호 조합을 출력

3️⃣ 코드 및 설명

내 코드

부분적으로 시간 초과


function solution(dice) {
    function combinations(arr, k) {
        const res = [];
        function dfs(start, comb) {
            if (comb.length === k) {
                res.push(comb.slice());
                return;
            }
            for (let i = start; i < arr.length; i++) {
                comb.push(arr[i]);
                dfs(i + 1, comb);
                comb.pop();
            }
        }
        dfs(0, []);
        return res;
    }

    function getAllSums(diceIdxs) {
        let sums = [0];
        for (const idx of diceIdxs) {
            const faces = dice[idx];
            const temp = [];
            for (const s of sums) {
                for (const f of faces) {
                    temp.push(s + f);
                }
            }
            sums = temp;
        }
        return sums;
    }

    function countLess(arr, val) {
        let l = 0, r = arr.length;
        while (l < r) {
            const m = (l + r) >> 1;
            if (arr[m] < val) l = m + 1;
            else r = m;
        }
        return l;
    }

    const n = dice.length;
    const diceIdxs = Array.from({length: n}, (_, i) => i);
    const choose = n / 2;
    let maxWin = -1;
    let best = [];

    for (const comb of combinations(diceIdxs, choose)) {
        const rest = diceIdxs.filter(x => !comb.includes(x));
        const aSums = getAllSums(comb).sort((a, b) => a - b);
        const bSums = getAllSums(rest).sort((a, b) => a - b);

        let win = 0;
        for (const a of aSums) {
            win += countLess(bSums, a);
        }
        if (win > maxWin) {
            maxWin = win;
            best = comb.map(x => x + 1).sort((a, b) => a - b);
        }
    }
    return best;
}

모범 코드


function solution(dice) {
    // n/2개 조합 만들기
    function combinations(arr, k) {
        const res = [];
        function dfs(start, comb) {
            if (comb.length === k) {
                res.push(comb.slice());
                return;
            }
            for (let i = start; i < arr.length; i++) {
                comb.push(arr[i]);
                dfs(i + 1, comb);
                comb.pop();
            }
        }
        dfs(0, []);
        return res;
    }

    // 주사위 인덱스 배열로 만들 수 있는 모든 합의 배열 반환
    function getAllSums(diceIdxs) {
        let sums = [0];
        for (const idx of diceIdxs) {
            const faces = dice[idx];
            const temp = [];
            for (const s of sums) {
                for (const f of faces) {
                    temp.push(s + f);
                }
            }
            sums = temp;
        }
        return sums;
    }

    // 이분탐색: arr에서 val 미만의 개수
    function countLess(arr, val) {
        let l = 0, r = arr.length;
        while (l < r) {
            const m = (l + r) >> 1;
            if (arr[m] < val) l = m + 1;
            else r = m;
        }
        return l;
    }

    const n = dice.length;
    const diceIdxs = Array.from({length: n}, (_, i) => i);
    const choose = n / 2;
    let maxWin = -1;
    let best = [];

    for (const comb of combinations(diceIdxs, choose)) {
        const rest = diceIdxs.filter(x => !comb.includes(x));
        const aSums = getAllSums(comb).sort((a, b) => a - b);
        const bSums = getAllSums(rest).sort((a, b) => a - b);

        let win = 0;
        for (const a of aSums) {
            win += countLess(bSums, a);
        }
        if (win > maxWin) {
            maxWin = win;
            best = comb.map(x => x + 1).sort((a, b) => a - b);
        }
    }
    return best;
}

주사위 고르기

1️⃣ 문제

2️⃣ 문제 해결 전략

3️⃣ 코드 및 설명

4️⃣ 시간복잡도