[JavaScript] 프로그래머스: 주사위 고르기

난이도 : Level 3
알고리즘 유형 : 조합, 이분 탐색
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/258709

 

 

문제 풀이

• 승률 계산 방식
      A가 선택한 주사위에서 나올 수 있는 수를 저장한 배열 => arrA
      B가 선택한 주사위에서 나올 수 있는 수를 저장한 배열 => arrB
          arrA에서 반복문을 돌면서 각 결과값이 이기는 횟수 세기.
  1. [ 조합 ] 선택할 수 있는 주사위의 조합 구하기.
  2. [ 조합 ] 선택된 주사위 조합에서 나올 수 있는 결과의 값 구하기.
  3. [ 이분 탐색 ] 선택된 주사위의 결과 값에서 반복문을 돌면서 선택되지 않은 값 중에서 이기는 횟수 구하기.

 

A가 승률이 높은 주사위들의 조합을 찾기 위해 모든 조합을 살펴보며 승률을 확인해야한다. $ O({}_{n}C_{n / 2}) $

아래 코드는 주사위들의 index를 배열에 저장하며 모든 조합의 배열을 반환하는 함수이다.

function generateCombination(n, c){
    const result = [];
    function combination(idx, path) {
        if(path.length === c) {
            result.push(Array.from(path));
            return;
        }
        for(let i=idx; i<n; i++){
            path.push(i);
            combination(i+1, path);
            path.pop();
        }
    }
    combination(0, []);
    return result;
}

 

그럼 이제 선택될 주사위들의 index를 구했으니 실제로 선택된 다이스들을 배열에 담아 반환하는 함수를 선언할 것이다.

그리고 B가 선택한 주사위는 A가 선택하지 않은 주사위들이 된다.

function getDices(chosen, dice, N) {
    const diceA = [], diceB = [];
    
    let idx=0;
    for(let i=0; i<N; i++){
        if(chosen[idx] === i) {
            diceA.push(dice[i]); idx++;
        }
        else diceB.push(dice[i]);
    }
    
    return [diceA, diceB];
}

 

그럼 각 A와 B가 선택한 주사위에서 나오는 결과값들을 반환하는 함수는 아래와 같다. $ O(6^{n / 2}) $

function getOutcomes(dices, N) {
    const result = [];
    function combination(idx, sum){
        if(idx === N){
            result.push(sum);
            return;
        }
        
        for(let i=0; i<6; i++) combination(idx + 1, sum + dices[idx][i]);
    }
    combination(0, 0);
    return result;
}

 

A의 주사위 결과값들을 살펴보며, 이분탐색으로 승률을 계산하는 함수는 아래와 같다. $ O(6^{n / 2} \times \log(6^{n / 2})) $

function calculateWinCount(arrA, arrB) {
    let count = 0;
    
    arrA.forEach((v) => {
        let left=0, right = arrB.length - 1, mid;
        let rowCount = -1;
        
        while(left <= right) {
            mid = Math.floor((left + right) / 2);
            
            if(arrB[mid] < v){
                rowCount = Math.max(mid, rowCount);
                left = mid + 1;
            }
            else right = mid - 1;
        }
        count += rowCount + 1;
    })
    
    return count;
}

 

 

전체 코드

function solution(dice) {
    const N = dice.length;
    
    const combinations = generateCombination(N, N / 2);
    let answer = [], answerCount = 0;
    
    combinations.forEach((comb) => {
        const [diceA, diceB] = getDices(comb, dice, N);
        
        const arrA = getOutcomes(diceA, N / 2);
        const arrB = getOutcomes(diceB, N / 2).sort((a, b) => a - b);
        
        const winCount = calculateWinCount(arrA, arrB);
        
        if(winCount > answerCount) {
            answer = comb;
            answerCount = winCount;
        }
    })
    
    return answer.map((v) => v + 1);
}

function generateCombination(n, c){
    const result = [];
    function combination(idx, path) {
        if(path.length === c) {
            result.push(Array.from(path));
            return;
        }
        for(let i=idx; i<n; i++){
            path.push(i);
            combination(i+1, path);
            path.pop();
        }
    }
    combination(0, []);
    return result;
}

function getDices(chosen, dice, N) {
    const diceA = [], diceB = [];
    
    let idx=0;
    for(let i=0; i<N; i++){
        if(chosen[idx] === i) {
            diceA.push(dice[i]); idx++;
        }
        else diceB.push(dice[i]);
    }
    
    return [diceA, diceB];
}

function getOutcomes(dices, N) {
    const result = [];
    function combination(idx, sum){
        if(idx === N){
            result.push(sum);
            return;
        }
        
        for(let i=0; i<6; i++) combination(idx + 1, sum + dices[idx][i]);
    }
    combination(0, 0);
    return result;
}

function calculateWinCount(arrA, arrB) {
    let count = 0;
    
    arrA.forEach((v) => {
        let left=0, right = arrB.length - 1, mid;
        let rowCount = -1;
        
        while(left <= right) {
            mid = Math.floor((left + right) / 2);
            
            if(arrB[mid] < v){
                rowCount = Math.max(mid, rowCount);
                left = mid + 1;
            }
            else right = mid - 1;
        }
        count += rowCount + 1;
    })
    
    return count;
}

 

 

회고

처음에 이 방법을 생각하고 선택한 주사위들의 조합 계산하기 + 선택된 주사위들의 결과값 구하기 + 이분 탐색으로 승률 계산하기를 생각했을 때, $ O({}_{n}C_{n / 2} \times ( 6^{n / 2} \times 2 + 6^{n / 2} \times \log(6^{n / 2}) )) $ 의 시간복잡도를 가지게된다.

막연히 6의 n/2 승 이라서 시간초과가 날 것이라고 생각했다.

달리 다른 방안이 생각나지 않아 일단 구현해보기로 했다 구현완료하고 제출하니까 시간초과가 나지 않았다!

생각해보니 n이 최대 10이라서 n이 10인 경우라해도 6 ^ 5은 7776 밖에 되지 않았다...

ㅎㅎ 앞으로는 시간복잡도가 구해졌으면 그 결과값도 한번 계산해보는 것으로 해야겠다!