프로그래머스 [Lv. 3] 주사위 고르기 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(dice) {
    const n = dice.length;
    const halfN = n / 2;
    const m = dice[0].length;
    
    const dictD = {};
    
    // n 개 중에서 n // 2개 고르기
    
    const dfs2 = (s, v, dk, tot) => {
        if (s == halfN) {
            dictD[dk].push(tot);
            return
        };
        for (let idx = 0; idx < 6; idx++) {
            dfs2(s+1, v, dk, tot+dice[v[s]][idx]);
        };
    };
    
    const dfs = (s, v) => {
        if (s == n) {
            if (v.length == halfN) {
                const dk = v.join("")
                dictD[dk] = [];
                dfs2(0, v, dk, 0);
            };
            return
        };
        
        dfs(s+1, [...v, s]);
        dfs(s+1, v)

    };
    dfs(0, []);
    
    const dictDKeys = Object.keys(dictD); 
    // 이진 탐색을 위해 정렬
    dictDKeys.forEach((k) => {
        dictD[k].sort((a, b) => a - b);
    });
    
    let answer = [];
    let maxWin = 0;
    
    const dfs3 = (s, a, b) => {
        if (s == n) {
            const aKey = a.join("");
            const bKey = b.join("");
            // a의 입장에서 a의 합 중 b의 합보다 큰 숫자의 개수
            // 이진 탐색
            const aValue = dictD[aKey];
            const bValue = dictD[bKey];
            const lenV = aValue.length;
            let cnt = 0;
            for (let jdx = 0; jdx < lenV; jdx++) {
                const cat = aValue[jdx];
                let left = 0;
                let right = lenV - 1;
                while (left <= right) {
                    const mid = parseInt((left + right) / 2);
                    const cbt = bValue[mid];
                    if (cbt < cat) {
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    };
                };
                cnt += left;
            };
            if (cnt > maxWin) {
                maxWin = cnt;
                answer = aKey.split("").map((e) => Number(e) + 1);
            }
            return;
        };
        
        if (a.length < halfN) {
            dfs3(s+1, [...a, s], b);
        };
        if (b.length < halfN) {
            dfs3(s+1, a, [...b, s]);
        };
    };
    dfs3(0, [], []);
    return answer;
}

풀이 방법

1. 조합을 이용해 키를 만든다.
   1. 조합은 dfs를 이용한다.
   2. 키는 선택한 주사위의 번호가 된다. => dk
   3. 선택한 주사위들을 바탕으로 다시한번 조합을 만든다.
      1. 예를 들어 A가 1번 [1, 2, 3, 4, 5, 6]과 4번 [1, 1, 4, 4, 5, 5] 주사위를 고른 경우
      2. 1+1, 1+1, 1+4, ... , 6+4, 6+4, 6+5 까지 총 36개를 dk가 키인 배열에 push 한다.
   4. 만들어진 dk의 조합에 배열을 모두 채운 다음 정렬을 해서 이진탐색을 준비한다.
2. a와 b의 조합을 나누고 키를 만든다.
   1. a가 [1, 4]이고 b가 [2, 3]인 경우 14와 23이 각각의 키가 된다.
   2. 키를 통해 value를 가져오면 앞서 만든 배열이 정렬되서 나온다.
      1. a를 예로 들면 [2, 2, ... , 11, 11] 이 된다.
   3. 정렬된 a의 값을 b에서 찾는데 a보다 크거나 같은 값이 나올 때까지 찾는다.
      1. 이 과정에서 이진탐색을 이용하며 b의 index값이 곧 a가 이길 수 있는 b의 조합이 된다.
         1. 간단하게 a가 [1, 2, 3, 4, 5, 6]의 숫자 합을 가지고 b가 [1, 1, 2, 2, 3, 3]의 숫자 합을 가진다면
         2. a가 3 일때 b의 index는 4이 되며 a가 3일 때는 4번 이길 수 있다는 말이 된다.
      2. 이런식으로 b의 index인 left값을 cnt에 전부 더한다.
   4. cnt를 이제 maxWin값과 비교한다.
      1. maxWin값보다 큰 경우
      2. answer값에 현재 고른 조합을 넣는다.
3. 마지막으로 answer를 반환하면 끝난다.

 

느낀점

• 최대한 알고 있는 알고리즘을 전부 사용해봤다.
• dfs를 통해서 조합을 만들고
• dfs를 통해서 a와 b로 나누는 조합도 만들고
• dfs를 통해서 halfN의 개수만큼 조합을 만들어서 주사위의 조합을 또 조합을 통해 합으로 만들고 저장할 수 있었다.
• 해시 알고리즘을 통해서 키 값을 배열에서 string으로 바꾼 후 value를 저장했다.
• 마지막으로 이진탐색을 통해서 현재 숫자 합보다 큰 값을 찾고 몇 개를 이길 수 있는지 계산할 수 있었다.
• 결과적으로 dfs 세 번, 해시 한 번, 이진탐색 한 번을 이용한 알고리즘 집약 그 자체 였다.