[프로그래머스] Lv3. 주사위 고르기 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 3

출처 : 프로그래머스 - 주사위 고르기

문제

제한사항

📌 내가 생각한 풀이

조합을 이용해서, 우선 주사위를 고르는 경우의 수를 모두 구하자. 그 다음 고른 주사위 번호에 대한 주사위를 2차원 배열로 담고, 백트래킹을 사용하여, 주사위 값의 합을 만들자. 이때 Map을 사용하여, 중복값은 +1로 해주자.

const getCombination = (arr, selectNum) => {
  let result = [];
  if (selectNum === 1) return arr.map(d => [d]);
  arr.forEach((fixed, idx, origin) => {
    let rest = origin.slice(idx + 1);
    let combination = getCombination(rest, selectNum - 1);
    let attached = combination.map(d => [fixed, ...d]);
    result.push(...attached);
  });
  return result;
};

function solution(dice) {
  var answer = [];
  let diceNum = dice.length;
  let max = 0;
  let numArr = new Array(diceNum).fill().map((d, i) => i);
  let combi = getCombination(numArr, diceNum / 2);
  let trash = getCombination([1, 2, 3, 4, 5, 6], 1);
  let combiLen = combi.length;

  const backtracking = (result, arr, depth, map) => {
    let newResult = result;
    if (depth === diceNum / 2) {
      let sum = result.reduce((prev, now) => (prev += now));
      if (map.get(sum)) map.set(sum, map.get(sum) + 1);
      else map.set(sum, 1);
      return;
    }
    for (var z = 0; z < 6; z++) {
      newResult.push(arr[depth][z]);
      backtracking(newResult, arr, depth + 1, map);
      newResult.pop();
    }
  };

  for (var i = 0; i < combiLen; i++) {
    let result = 0;
    let a = combi[i];
    let b = numArr.slice().filter(d => !a.includes(d));
    let aDice = [];
    let bDice = [];
    let aMap = new Map();
    let bMap = new Map();
    a.forEach(data => {
      aDice.push(dice[data]);
    });
    b.forEach(data => {
      bDice.push(dice[data]);
    });
    backtracking([], aDice, 0, aMap);
    backtracking([], bDice, 0, bMap);

    for (var [aVal, aCount] of aMap) {
      for (var [bVal, bCount] of bMap) {
        if (aVal > bVal) result += aCount * bCount;
      }
    }
    if (result > max) {
      max = result;
      let nA = a.map(d => (d += 1));
      answer = nA;
    }
  }
  return answer;
}

📌 느낀점

처음 내가 생각했을 땐, Map을 사용하지 않고, hash 테이블을 만들어 시도하였지만, 해시값을 entry로 바꾸어주는데 불필요한 연산이 필요하다고 생각하여 Map객체를 사용하였다.