주사위 고르기 [자바]

 

🧫 문제 분석

✔️ 출처

주사위 고르기 level 3

📖 문제

 

많은 공부가 된 문제다..

 

문제 풀이 방법까지는 잘 도출했는데

 

정작 최대 5개를 뽑았을때

주사위의 눈의 합을 구하는 법에서 막혔다.

 

문제는 너무 많은 생각이라고 생각한다. 

 

나오는 모든 합에 대하여 카운트를 해주려다가 이건 또 너무 복잡하고

머리가 잘 안돌아갔다.

 

 

이번에 알게된 것

 

N개의 조합의 모든 합 구하기

dfs로 짜는 것 까진 했는데 

정작 어떻게 더해야할지 감이 안잡혔다. 

근데 그냥 하나하나씩 주사위를 건드리면 됐다.

1번 주사위의 i번째 + 2번 주사위의 i번째.. 이런식으로 

 

잘 기억해두자..

 

 

이분 탐색

최대 개수를 구할때는 

size() 까지 해줘해한다는 것

 

처음에 탐색 범위를 0 ~size()-1 까지로 했는데

12번 테스트 케이스가 계속 틀렸다.

 

인덱스로 개수를 셀때는  size()까지로 하자.

 

예시

target이하의 개수를 세는 문제일떄 

[1,2,3,4] 일때 target이 5이면

idx = 4로 4가지를 가질 수 있기때문에

0~size() 까지 탐색

 

 

 

---

🔅 문제 풀이

import java.util.*;

class Solution {

    static int n;
    static int[][] dice1;
    static List<int[]> A;

    
    
    public int[] solution(int[][] dice) {
        n = dice.length;
        dice1 = dice;
        A = new ArrayList<>();
        
        int max = 0;
        
        int[] answer = new int[n/2];
        // 우선 n/2가지를 뽑는다.
        makeCombine(0, 0, new int[n/2]);
        
        
        for (int[] aDice : A) {
            
            // 반대 쪽도 생성
            int[] bDice = makeBConbine(aDice);
        
            // 뽑은 주사위로 모든 합의 조합을 생성
            List<Integer> sumA = new ArrayList<>();
            List<Integer> sumB = new ArrayList<>();
            
            sumDice(aDice, 0,0, sumA);
            sumDice(bDice, 0,0, sumB);
            
            Collections.sort(sumB);
            
            // 이분 탐색으로 개수 구하기
            
            int cnt = 0;
            
            for (int i = 0; i < sumA.size(); i++) {
                int target = sumA.get(i);
                
                int tmpCnt = 0;
                int left = 0, right = sumB.size();
                
                while(left < right) {
                    int mid = (left + right) >>> 1;
                    
                    if (sumB.get(mid) < target) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                

                cnt += left;
                
            }
            
            
            // 최대면 값 생성
            if (max < cnt) {
                
                max = cnt;
                
                for (int i = 0; i < aDice.length; i++) {
                    answer[i] = aDice[i] + 1;
                }
            }
            
        }
        
        
        return answer;
    }
    
    private static void makeCombine(int idx, int depth, int[] tmp) {    
        if (depth == n/2) {
            A.add(tmp.clone());
            return;
        }
        for (int i = idx; i < n; i++) {
            tmp[depth] = i;
            makeCombine(i + 1, depth + 1, tmp);
        }
    }
    
    private static int[] makeBConbine(int[] aDice) {
        int[] b = new int[n/2];
        
        boolean[] isAdice = new boolean[n];
        
        for (int i = 0; i < aDice.length; i++) {
            isAdice[aDice[i]] = true;
        }
        
        int idx = 0;
        for (int i = 0; i < n; i++) {
            if (!isAdice[i] ) {
                b[idx++] = i;
            }
        }
        
        return b;
        
    }
    
    // 뽑은 주사위 배열, 주사위 idx, 합, 깊이, 합을 저장할 리스트
    private static void sumDice(int[] dice, int idx, int sum, List<Integer> list) {
        if (idx == n/2) {
            list.add(sum);
            return;
        }
        
        for (int i = 0; i < 6; i++) {
            sumDice(dice, idx + 1, sum + dice1[dice[idx]][i], list);
        }
    }
    
}

 

 

🔅 리팩토링

❗ 오답노트 / 필요한 지식

1. 파라미터에 컬렉션이나 배열을 넘기는걸 싫어하지말자. 이것때문에 더 오래걸린것도 있다.