younganswer
Problem SolvingMar 20, 2026

[프로그래머스] 258709 주사위 고르기 (javascript)

#Problem Solving#Coding Test#Algorithm#Programmers#258709#Brute Force#Combinations#Simulation#Implementation
[프로그래머스] 258709 주사위 고르기 (javascript)

문제

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



풀이

문제 파악

먼저 문제를 읽고 총 실행 횟수와 시간 복잡도부터 계산해봤다.

사실 이 문제는 예전에 한 번 도전했다가 포기했던 문제인데, 당시에는 암산 실수로 전체 연산 횟수가 2억 회가 넘는다고 착각했고,

"이건 브루트포스로는 절대 안 되겠는데?"

라고 판단한 후, 알고리즘이 떠오르지 않아 그대로 손을 놓았던 기억이 있다.

하지만, 다시 계산해보니 핵심 연산에 해당하는 조합 계산과 주사위 합 계산이 아래와 같이

10C5∗65=252∗7776=1,958,112_{10}C_5 * 6^5 = 252 * 7776 = 1,958,112

로, 약 200만 회 정도로 충분히 브루트포스 방식으로도 해결할 수 있는 규모였다.


접근 방식

브루트포스로 방향을 결정한 후에는 흔히 말하는 '빡구현' 문제를 풀이하는 형식으로 접근했다. 복잡하게 최적화를 고민하기 보다는, 명확하고 빠르게 문제에서 요구하는 단계를 그대로 함수 단위로 나누어 구현했다.

풀이 흐름은 다음과 같다.

  1. 조합 계산: nn개의 주사위 중 n2\frac{n}{2}개를 고르는 모든 조합 생성
  2. 보완 집합 계산: 선택되지 않은 나머지 주사위 고르기
  3. 주사위 합 생성: 선택된 주사위들이 만들 수 있는 모든 합 계산
  4. 승리 횟수 계산: 집합 A, B 간에 서로에 대한 승리 횟수 계산
  5. 최적 조합 계산: 모든 경우에 대해 가장 승리 횟수가 높은 조합 선택

'빡구현'이다 보니 코드를 빠르게 작성하되 헷갈리지 않게 잘 읽히게 작성하려고 노력했다.


조합 계산은 최대 10C5_{10}C_5, 주사위 합 생성은 최대 656^5, 승리 횟수 계산은 최대 65×656^5 \times 6^5 규모가 된다. 전체적으로 보았을 때 연산량은 2억 회 이내로 여유롭게 들어오기 때문에, 사실 크게 최적화에 신경쓸 필요는 없다고 생각한다.

다만 승리 횟수 계산 과정에서 선택 집합과 보완 집합의 비교가 항상 2번 씩 발생하고(calc(A, B), calc(B, A)), 내부 주사위 합이 정렬되어 있을 때, 투포인터, 이진 탐색 등의 최적화가 가능하다고 생각해서, 승리 횟수 계산 부분에서는 조금의 최적화를 시도해봤다.


javascript 특징과 주의점

추가로, JavaScript에 익숙하지 않아 몇 가지 사소한 실수를 겪었다. TypeScript만 주로 사용하다 보니 놓치고 있던 부분들이었는데, 이번 문제를 통해 다시 한 번 정리하게 되었다.

구현 과정에서 주의해야겠다고 느낀 점들은 다음과 같다.

  1. sort 함수는 기본적으로 문자열로 정렬하기 때문에, 숫자 배열을 정렬할 때는 arr.sort((a, b) => a - b)와 같이 비교 함수를 명시적으로 전달해야 한다.
  2. javascript의 Number 타입은 64-bit 부동소수점(IEEE 754)이며 double과 유사하다. 따라서 나누기 연산을 할 때, 정수 나눗셈이 필요한 경우 주의해야한다. 예를 들어, n / 2는 n이 홀수일 때 소수점이 포함된 결과가 나오므로, 정수 나눗셈이 필요한 경우 Math.floor(n / 2) 또는 n >> 1과 같이 처리해야 한다.
  3. 참조에 주의해야한다.
    1. Array(n).fill(value)는 모든 요소가 같은 객체를 참조하기 때문에 특정 원소를 변경하면 모든 요소가 변경되는 부작용이 발생할 수 있다. 따라서 배열을 초기화할 때는 Array.from({ length: n }, () => value)와 같이 각 요소가 독립된 객체를 참조하도록 해야 한다.
    2. Map, Set에서 객체를 key로 사용할 때는 equal이 아닌 same reference로 비교하기 때문에 주의해야한다.


정답 코드

javascript
const combinations = (n, size) => {
    const dfs = (start, combination) => {
        if (combination.length === size) {
            return [combination];
        }
        
        return Array
            .from({ length: n - start }, (_, index) => index + start)
            .reduce(
                (acc, index) => [
                    ...acc,
                    ...dfs(index + 1, [...combination, index])
                ],
                []
            );
    };

    return dfs(0, []);
};

const complement = (combination, n) => 
    Array
        .from({ length: n }, (_, index) => index)
        .filter(index => (new Set(combination)).has(index) == false);

const buildSums = (dice, combination) =>
    combination.reduce(
        (sums, index) =>
            sums.reduce(
                (acc, sum) => [
                    ...acc,
                    ...dice[index].map(face => sum + face)
                ],
                []
            ),
        [0]
    );

const createSumGetter = (dice) => {
    const cache = new Map();

    return (combination) => {
        const key = combination.join(",");

        if (cache.has(key) == false) {
            cache.set(
                key,
                buildSums(dice, combination).sort((a, b) => a - b)
            );
        }

        return cache.get(key);
    };
};

const lowerBound = (arr, target) => {
    let l = 0;
    let r = arr.length;

    while (l < r) {
        const mid = (l + r) >> 1;
        arr[mid] < target ? (l = mid + 1) : (r = mid);
    }

    return l;
};

const calcWins = (a, b) => {
    let wins = 0;

    for (let i = 0; i < a.length;) {
        const value = a[i];
        let count = 0;

        while (a[i] === value) {
            i++;
            count++;
        }

        wins += lowerBound(b, value) * count;
    }

    return wins;
};

const bestCombinations = (combinations, getSums, n) => {
    let bestComb = [];
    let bestScore = -Infinity;

    const limit = combinations.length / 2;

    for (let i = 0; i < limit; i++) {
        const A = combinations[i];
        const B = complement(A, n);

        const sumsA = getSums(A);
        const sumsB = getSums(B);

        const scoreA = calcWins(sumsA, sumsB);
        const scoreB = calcWins(sumsB, sumsA);

        if (bestScore < scoreA) {
            bestScore = scoreA;
            bestComb = A;
        }

        if (bestScore < scoreB) {
            bestScore = scoreB;
            bestComb = B;
        }
    }

    return bestComb;
};

const solution = (dice) => bestCombinations(
    combinations(
        dice.length,
        dice.length >> 1
    ),
    createSumGetter(dice),
    dice.length
).map(i => i + 1).sort((a, b) => a - b);

Share this post

N