[JS] 주사위 고르기

DFS(완전탐색) + 조합 + Map 자료형 을 조합해서 풀었다.

 

 

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

프로그래머스

 

처음에는 단순하게 완전탐색 + 조합을 활용해서 해결해보려 했다.

 

조합을 활용해서 모든 주사위 눈의 경우의수를 얻어낸 후 해당 주사위 조합마다 완전탐색을 활용하여 cnt를 계산했다.

하지만 이방식의 경우 이 문제를 풀 수 없다.

 

최대 주사위가 10개이므로

 

6 * 10 (완전탐색) * 10C5 의 시간복잡도가 만들어져 해결을 할 수 없고 실제로도 시간초과가 떴다.

 

따라서 완전탐색을 하는 부분을 줄여보기로 했다.

 

한 조합 (예를들어 [0,1] , [2,3] 번째) 에서 A가 B를 이기는 횟수를 구하기 위해서는 각 주사위로 조합되어 나올 수 있는 주사위 수의 합을 계산하면 된다.

 

 

만약 첫번째 예시를 예로 들어서 0,1번째 주사위를 굴려 나올수 있는 합의 경우의 수는

[4,4,4,4,5,5,5,5,5,5,6,6,...... ] 6* 6 총 36개가 된다.

 

마찬가지로 B의 주사위도 6*6 총 36개의 경우가 나온다.

 

이제 A합 배열을 순회하며 A배열안의 값보다 작은 B값의 개수들을 더해서 cnt를 구할 수 있다.

 

하지만 이방식도 문제가 있다. 주사위가 5개라며 합의 배열은 6*5의 크기로 나오게 된다.. 결국 이전에 방식과 차이가 없게된다. 이런경우 고려해볼만할 방식은 3가지 정도가 있는 듯 하다.

 

1. 이분탐색

어차피 한 값이 B배열에서 큰 값들을 알아야 하므로 배열을 만들때 정렬을 하고 이분탐색으로 찾는 방법을 쓸만하다.

2. 우선순위 큐

우선순위 큐도 1번과 비슷한 맥락으로 쓸만하다.

3. Map 자료형 활용

배열을 보면 합이 중복되는 경우가 많아 Map자료형을 활용하여 cnt를 계산하면 시간을 많이 줄일 수 있을 겉 같았다.

 

3가지 방법중에서 구현하기 간단한 3번을 적용해 보았더니 시간초과가 해결되었다.

 

 

 

 

 

 

//조합 구하기
const combination = (ary,n) => {
    if(n===1) return ary.map(v =>[v])
    const ret = []
    
    ary.forEach((fixed,idx) => {
        const rest = ary.slice(idx+1)
        const combinations = combination(rest,n-1)
        const attach = combinations.map(v => [fixed,...v])
        ret.push(...attach)
    })
    return ret
}

function solution(dice) {

    //주사위를 굴려 합을 map 자료형으로 저장
    const rollDice = (ary,dice,map) => {
        if(ary.length===dice.length) {
            const sum = ary.reduce((a,c) => a+c,0)
            if(map.get(sum)) map.set(sum , map.get(sum)+1)
            else map.set(sum,1)
            return
        }
        const ret = []
        for (let i = 0 ; i < 6 ; i++){
            ary.push(dice[ary.length][i])
            rollDice(ary,dice,map)
            ary.pop()
        }
        return ret
    }
    
    //결과값을 저장할 공간
    let retAry = []
    let retCnt = 0
    
    //dice를 번호로 나타내기위한 배열
    const diceIdx = [...Array(dice.length)].map((_,i) => i)
    //조합 가져오기
    const combinations = combination(diceIdx,dice.length/2)
    
    
    for (const aAry of combinations){
        //이번 조합에서의 a,b다이스
        const aDice = aAry.map(v => dice[v])
        const bDice = diceIdx.filter(v=>!aAry.includes(v)).map(v => dice[v])
        
        //굴린 주사위의 정보를 map자료형으로 가져옴
        const aMap = new Map()
        const bMap = new Map()
        rollDice([],aDice,aMap)
        rollDice([],bDice,bMap)
        let ret = 0
        
        //이번 조합에서의 승리 횟수를 구함
        for (const [aCurSum,aCnt] of aMap){
            for (const [bCurSum,bCnt] of bMap){
                if(aCurSum > bCurSum) ret += aCnt * bCnt
            }
        }

        //결과값 업데이트
        if (ret > retCnt){
            retAry = aAry
            retCnt = ret
        }
    }
    //주사위가 1부터 시작이라 바꿔줌
    return retAry.map(v => v+1)
}