[프로그래머스 / js] 주사위 고르기

문제

 

A와 B가 n개의 주사위를 가지고 승부를 한다. 각 주사위의 6개의 면에는 하나의 숫자가 쓰여있으며 각 면이 나올 확률은 동일하다
각 주사위는 1~n의 번호를 가지고 있고 주사위에 쓰인 수의 구성을 모두 다르다
A와 B가 각자 n/2개의 주사위를 가져가고 이 주사위들을 굴려서 나온 수의 합이 더 큰 쪽이 승리한다

2차워 정수 배열 dice가 주어질 때 A가 승리할 확률이 가장 높은 주사위 조합을 오름차순으로 1차원 정수 배열에 담아 return 하라!

제한사항

dice배열의 길이는 2이상 10이하이며 2의 배수이다
dice[i]는 i+1번의 주사위에 쓰인 6개의 수를 담고 있다
dice[i]의 원소들은 1이상 100이하이다

입출력 예

 

 

풀이

 

1. 주사위 n/2개씩 나누는 조합을 구한다 (dfs)
2. 구한 조합에 대해 주사위를 굴려 나올 수 있는 수의 합을 구한다 (dfs)
3. 이 수를 이진 탐색으로 비교하여 이기는 횟수를 구한다

4. max_win을 두고 이긴 횟수와 비교하여 최댓값을 갱신하여 승리할 확률이 가장 높은 주사위 조합을 구하면 완료!

 

ex
[0,1] [2,3] 으로 주사위를 나눠 가진다면 0,1주사위를 굴려 나오는 수의 합과 2,3을 굴려 나오는 수의 합을 각각 구하여 배열에 저장하고 이 값들을 비교하여 이긴 횟수를 구한다

 

function solution(dice) {
  var answer = [];

// 주사위를 굴려 나오는 수의 합 구하는 함수
  function check_sum(n, arr, s, res) {
    if (n === arr.length) {
      res.push(s);
      return;
    }
    for (let i = 0; i < dice[arr[n]].length; i++) {
      check_sum(n + 1, arr, s + dice[arr[n]][i], res);
    }
  }

  let sum = [];
  // 주사위 조합 구하는 함수
  function choose_dice(num, my, k) {
    if (num === dice.length / 2) {
      sum.push(my);
      return;
    }
    for (let i = k + 1; i < dice.length; i++) {
      choose_dice(num + 1, [...my, i], i);
    }
  }

//1
  for (let i = 0; i < dice.length; i++) {
    choose_dice(1, [i], i);
  }

// 이기는 횟수를 구하기 위한 이진 탐색
  function binary_search(num, arr) {
    let left = 0;
    let right = arr.length - 1;
    if (num > arr[right]) return right + 1;
    while (left < right) {
      let mid = ~~((left + right) / 2);
      if (arr[mid] < num) left = mid + 1;
      else right = mid;
    }
    return left;
  }

  let max;
  let max_win = 0;
  for (let i = 0; i < sum.length / 2; i++) {
    let my_res = [];
    let op_res = [];
    //2
    check_sum(0, sum[i], 0, my_res);
    check_sum(0, sum[sum.length - 1 - i], 0, op_res);
    let m_c = 0;
    let o_c = 0;
    my_res.sort((a, b) => a - b);
    op_res.sort((a, b) => a - b);
    //3
    for (let j = 0; j < my_res.length; j++) {
      let temp = binary_search(my_res[j], op_res);
      m_c += temp;
    }
    for (let j = 0; j < op_res.length; j++) {
      let temp = binary_search(op_res[j], my_res);
      o_c += temp;
    }
    //4
    if (m_c > o_c && m_c > max_win) {
      max = sum[i];
      max_win = m_c;
    } else if (o_c > max_win) {
      max = sum[sum.length - 1 - i];
      max_win = o_c;
    }
  }
  answer = max.map((a) => a + 1);
  return answer;
}

 

3에서 이진탐색을 사용하지 않고 반복문을 돌아 확인할 경우 시간 초과가 나서 통과할 수 없었다 이진탐색을 사용하니 성공!!