프로그래머스: 주사위 고르기 - javascript(조합, dfs, 이분탐색)

문제 출처 

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

프로그래머스

전체 흐름 

아무래도 문제의 전체흐름과 어떤 알고리즘을 사용했는지부터 짚고 가는 것이 좋겠다. 

 

1. 주사위 선택하기

- 조합 함수를 사용했다.  

- ex) n이 4일 때, 주사위는 1,2,3,4가 있다. 

=> 내가 주사위를 선택할 경우의 수는 "[1,2], [1,3],[1,4],[2,3],[2,4],[3,4]" 인 경우가 될 것이다. 

 

2. 선택할 주사위 중 각각 하나의 수 선택하기 

- dfs 완전탐색을 활용했다. 

- ex) 만약 내가 선택한 주사위가 1번 2번일 때 해당 주사위 구성은 각각 [1,2,3,4,5,6], [3,3,3,3,4,4] 라고 하자. 

=> 주사위당 숫자 하나씩 선택해서 그 합을 배열에 추가할 것이다. 

(여기서는 1번 주사위에서 1, 2번 주사위에서 3을 선을 선택한 후, 그 합을 배열에 추가한다) 

 

3. 내가 던진 주사위 중 나올 수 있는 모든 합과, 상대방이 던진 주사위 중 나올 수 있는 모든 합을 비교하기 

- 이분탐색을 활용했다. 

- 1번과 2번을 통해 주사위 합이 나올 수 있는 결과가 아래와 같이 나온다. 

- 그때 상대방은 3번과 4번 주사위 합이 나올 수 있는 결과가 아래와 같이 나온다. 

 

- "내가 던진 주사위의 합을 기준으로" 상대방의 합보다 클 경우가 몇번 있을지 구한다.  

ex) 여기서 4가 이길 경우의 수는 ? => 2번이다 (나는 4가 4개고, 상대방은 4보다 작은 수가 2개네(2가 2개)) 

 

4. 승률이 가장 높은 값 구하기. 

- Math.max()를 통해 값을 계속 갱신해줬다. 

문제 풀이 

자, 이제 함수를 들여다보자. 

 

1. 주사위 선택하기

 

- js의 대표적인 조합함수이기 때문에 설명은 자세히 하지 않겠다. 

- ex)  이 경우에 getCombination([1,2,3], 2) , 결과는 [[1,2][1,3][2,3]]이 되겠다. 

 

2. 선택할 주사위 중 각각 하나의 수 선택하기 

 

- 내가 선택한 주사위의 구성을 받은 함수이다. 

ex) 1번, 2번 주사위를 선택할 경우 이 매개변수를 받는다. [ [1, 2, 3, 4, 5, 6], [3, 3, 3, 3, 4, 4]]

- 이 배열 combi의 길이만큼 dfs가 돌면 된다. 

ex) combi[0] 에서 숫자 하나 선택하기 "주사위 1번" => combi[1] 에서 숫자 하나 선택하기 "주사위 2번"

- 각 주사위에서 숫자를 선택할 때 반복문을 돌려준다. 

  - 이때, 6만큼 반복문을 돌려주면 된다. 주사위는 6면이기 때문에 !  

- 주사위 1과 주사위 2에서 숫자를 각각 선택했다면 그 합을 results에 push한다. 

 

그럼 결과는 아래와 같이 나온다. 

 

 

3. 내가 던진 주사위 중 나올 수 있는 모든 합과, 상대방이 던진 주사위 중 나올 수 있는 모든 합을 비교하기 

- 이분 탐색을 이용해서 내가 던진 주사위의 모든 합의 경우의 수가 상대방의 경우의 수에서 몇 번 이길 수 있는지 확인 할 것이다. 

- 생각보다 간단한 문제인데, 그 이유는 

 

- 즉, 내 합들은 기준이 되고, 상대방 합을 이분탐색을 통해 탐색하는 것이다.

  - 계속 구하는 것, 내 4보다 작은 경우 몇개? => 내 다음 4보다 작은 경우 몇개? => .... => 내 10보다 작은 경우 몇개? 

  - 위와 같은 과정을 하면서 내가 이기는 경우의 수를 모두 더한다. 

 

4. 위 함수들을 이용해서 답 구하기 

- 위 함수들을 이용해서 main 코드를 작성해보자. 

 

 

- n: 주사위가 몇개인지 센다. 

- arr:  주사위 조합을 구하기 위해서 구해줬다. 

ex) n이 4인 경우 [0,1,2,3] 을 배열로 생성했다. => 나중에 답을 낼 때는 +1씩 해줘야 한다.  

- combinations : 조합 함수에 arr과 n/2를 매개변수로 넣는다. 

- oddCombinations: 상대방의 조합함수도 구해야 한다. 내가 [0,1]일 때 상대방은 [2,3] 조합이도록 구성 

 

아래는 주석처리로 설명을 작성했다. 

우리가 그동안 작성한 함수를 잘 정리하기만 하면된다. !!!! 

 

- 끝 - 

정답 코드 

function solution(dice) {
  let n = dice.length; 
  let arr = Array.from({length: n}).map((_, idx) => idx)
  let combinations = getCombination(arr, n/2)
  let oddCombinations = combinations.map((combi) => arr.filter(el => !combi.includes(el)))
  let max = 0; 
  let answer = [];   
    for(let i=0; i<combinations.length; i++){
       let aDices = combinations[i].map(el => dice[el])
       let bDices = oddCombinations[i].map(el => dice[el])

       let aSums = selectNum(aDices)
       let bSums = selectNum(bDices)
        
       let temp = versus(aSums, bSums)
        if(temp > max){
            max = temp
            answer = combinations[i]
        }
       }
    return answer.map(el => el+1); 
    
 function versus(arr1, arr2){
    let results = 0; 
    arr1.sort((a,b) => a-b)
    arr2.sort((a,b) => a-b)
    for(let i=0; i<arr1.length; i++){
       let value = arr1[i]
       let start = 0; 
       let end = arr2.length-1; 
      while(start<= end){
        let idx = parseInt((start+ end) / 2)
        if(value <= arr2[idx]){
            end = idx-1
        }else if(value > arr2[idx]){
            start = idx+1
        }
       }
      results += (start)
    }
    return results
}   
    
function selectNum(combi){ 
    let results = []; 
    function dfs(L, sum){
        if(L === combi.length){
           results.push(sum)
           }else{
               for(let i=0; i<6; i++){
                    dfs(L+1, sum + combi[L][i])
               }
          }
    }
    dfs(0,0)
    return results
}    
    
function getCombination(arr, selectNum){
    let results = []
    if(selectNum === 1) return arr.map(v => [v])
    arr.forEach((fixed, idx, origin) => {
        const rest = origin.slice(idx+1); 
        const combinations = getCombination(rest, selectNum -1)
        const attached = combinations.map((combi) => [fixed, ...combi])
        results.push(...attached)
    })
    return results
}
}