[프로그래머스][백트래킹][이분탐색][조합] 주사위 고르기

     

목차

 

 

 

문제

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

프로그래머스

 

코드 구현 시 주의점

일단 문제의 호흡이 굉장히 길다. 그래서 더 힘들었다..

 

 

코드 구현 방향

1. a b의 주사위를 조합에 맞게 서로 가져가기 -> dfs를 통한 조합식

2. a b의 주사위에서 모든 숫자를 더한 배열 만들기 -> 백트래킹을 통한 배열

3. a b합 배열을 비교해서 탐색하기 -> 이분탐색

 

ex)

#1 [1, 2, 3, 4, 5, 6]

#2 [1, 1, 1, 1, 1, 1]

#3 [1, 2, 2, 2, 2, 2]

#4 [2, 2, 2, 2, 2, 2]

 

 

1. 실행 시 6가지 중 1가지 경우

a:#1, #2      b: #3, #4

 

2. 케이스에 대한 2번 실행

a-> [2, 2, 3, 4, 5, 6 ......]     b -> [3, 3, 3, 3, 3, 3, 4 ......]  (이때 이분탐색을 해야하므로 정렬시킨 배열)

 

3. 케이스에 대한 3번 실행

a에서 5를 선택한 경우 b가 4이기 전의 개수만큼 a가 이기는 경우이다.

 

 

 

코드 구현

function sumCombi(dicecom, n){
    let ans = [];
    function choicing(idx, sum){
        if(idx === n){
            ans.push(sum)
            return;
        }
       for(let i=0; i< 6; i++){
            choicing(idx+1, sum+dicecom[idx][i]);
       }
    }
    choicing(0, 0);
    return ans;
}

function binarySearch(b, tg) {
    let left = 0, right = b.length - 1;
    let result = -1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (b[mid] < tg) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result + 1;
}

function solution(dice) {
    var answer = [];
    let answerCand = [];
    let len = dice.length;
    let choice = Math.floor(len/2);
    let dicecom = new Map();

    let idx =-1;
    function combi(idx){
        if(dicecom.size === choice){
            let dicecom2 = new Map();
            for(let i=0; i< len; i++){
                if(!dicecom.has(i))
                    dicecom2.set(i, dice[i]);
            }
            let diceA = [];
            let diceB = [];
            for(let v of dicecom.values()){
                diceA.push(v);
            }
            for(let v of dicecom2.values()){
                diceB.push(v);
            }
            let a = sumCombi(diceA, choice);
            let b = sumCombi(diceB, choice);
            
            a.sort((x, y)=> x-y);
            b.sort((x, y)=> x-y);
    
            let cnt =0;
            for(let diceA of a){
               cnt+= binarySearch( b, diceA);
            }
            let keys =[];
            for(let key of dicecom.keys()){
                keys.push(key);
            }
            answerCand.push([keys,cnt]);

            return;
        }
        for(let i = idx+1; i<len; i++){
            dicecom.set(i, dice[i]);
            combi(i);
            dicecom.delete(i);
        }
    }
    
    combi(idx);
    let final = answerCand.sort((a,b)=> b[1]-a[1])[0][0];
    answer = final.map((item)=>item+1).sort((a,b)=>a-b);

    return answer;
}