프로그래머스 (카카오 기출) | LV.3 주사위 고르기 - 완전탐색 & 이분탐색 문풀 (Java)

⬛ 프로그래머스 (카카오 기출) | LV.3 주사위 고르기 - 완전 탐색 & 이분탐색 문풀

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

프로그래머스

문제 설명1

문제 설명 2

---

💚문제 접근 방식

이해한 내용을 토대로 풀이 방식을 정리하였다.

풀이 코드 설명

주어진 주사위 배열에서 A와 B가 각각 N/2개의 주사위를 선택하여 주사위를 굴린 후, A가 이길 수 있는 경우의 수를 구하여 문제를 해결해야 하는 문제였다.

• 모든 주사위의 구성 조합을 생성하고, 각각의 구성에서 주사위를 굴려 이길 수 있는 경우의 수를 계산하면 가장 많은 승률 가진 조합을 선택한다.
• 가능한 모든 주사위 조합에 대해 A가 승리하는 경우의 수를 구하고, 그 승률이 가장 높은 주사위 조합을 찾는 문제이다.
• 크게 1) A가 가져갈 주사위를 선택하는 combination 부분과 2) 주사위 굴린 결과를 계산 calculate하는 부분으로 나눌 수 있다.

1) 각 팀(A와 B)이 뽑을 수 있는 주사위의 모든 조합을 combination (완.탐)으로 생성한 다음

2) 각 팀에서 각각의 주사위 조합으로 만들 수 있는 모든 눈의 합의 경우의 수를 calculate 하여 List에 담고 정렬한다. (이분탐색 하기 위함)

3) A가 던진 주사위의 각 눈의 합을 기준으로 B가 던진 주사위의 눈의 합 중에서 이기는 경우의 수를 이분 탐색을 통해 찾는다.

---

[ 풀이 상세 설명]

- 문제 케이스 1에서 A가 [1,4] 주사위를 가졌을 때를 기준으로 설명한다.

주사위 구성 조합 구한 뒤, A, B 각각 낼 수 있는 합의 구성을 구함

이분탐색을 통해 left를 구해서 누적한 게 승률이 되는 이유

---

💚 제출 코드

import java.util.*;

class Solution {
    static int diceCount;
    static boolean[] visited;
    static List<int[]> A = new ArrayList<>();
    static List<int[]> B = new ArrayList<>();
    
    static int[] result;
    static List<Integer> A_result;
    static List<Integer> B_result;
    
    // 재귀로 주사위 combination
    static void combination(int idx, int count){
        if(count == diceCount/2){
            int[] Atmp = new int[diceCount/2];
            int[] Btmp = new int[diceCount/2];
            
            int A_idx =0;
            int B_idx =0;
            for(int i=0; i<diceCount; i++){
                if(visited[i]){
                    Atmp[A_idx] = i+1;
                    A_idx++;
                }
                if(!visited[i]){
                    Btmp[B_idx] = i+1;
                    B_idx++;
                }
            }
            //각각의 조합 구성을 각 리스트에 담는다. 
            A.add(Atmp); 
            B.add(Btmp);
            return;
        }
        
        //전체 주사위 순회하면서
        for(int i=idx; i<diceCount; i++){
            visited[i] = true;
            combination(i+1, count+1);
            visited[i] = false;
        }
    }
    
    //calculate -> 각 눈의 합 종류 담음
    static void calculate(int idx, int[] dices, int[][] originDices, int sum, List<Integer> team){
        if(idx == dices.length){
            team.add(sum);
            return;
        }
        for(int i=0; i<6; i++){
            calculate(idx+1, dices, originDices, sum + originDices[dices[idx]-1][i], team);
        }
    }
    
    //솔루션 함수 
    public int[] solution(int[][] dice) {
        diceCount = dice.length;
        visited = new boolean[diceCount];
        
        //A,B에게 주사위 절반씩 나눌 수 있는 구성 전체 경우의 수 구함
        combination(0, 0);        
        
        int max = Integer.MIN_VALUE;
        int index = 0;
        
        for(int i=0; i<A.size(); i++){
            A_result = new ArrayList<>();
            B_result = new ArrayList<>();
            //A,B 각각 조합에 대한 주사위 눈 합
            calculate(0, A.get(i), dice, 0, A_result);
            calculate(0, B.get(i), dice, 0, B_result);
            //A,B 각각 조합에 대한 눈의 합 구한 리스트 오름차순 정렬 
            Collections.sort(A_result);
            Collections.sort(B_result);
            
            //A가 이길 경우를 구해야 함 
            int totalWinCount=0; 
            for(int a : A_result) { 
                //A 주사위의 조합으로 나올 수 있는 모든 합 각각을 돌면서
                int left = 0;
                int right = B_result.size();
                
                while(left+1 < right){
                    int mid = (left+right)/2; 
                    //A의 현재 합이 B의 중앙위치의 합보다 큰지 작은지에 따른 이분탐색 
                    if(a > B_result.get(mid)){
                        left=mid; //크다면 뒤쪽 범위에서 다시 탐색
                    }else right = mid;//작다면 앞쪽 범위에서 탐색 
                }
                //이기는 경우의 합을 다 더함
                totalWinCount += left;
                //left는 이분 탐색을 통해 찾은 값 중에서 현재 a가 B_result의 몇 번째 위치에 있는지를 나타냄
                //left로 발견한 값 : A의 현재 원소보다 작거나 같은 B의 가장 큰 원소가 담겼다는 말
                //따라서, 그 인덱스 자체가 결국 (A가 이기는 경우의 수)가 된다.
            }
            //가장 큰 승률로 갱신
            if(max < totalWinCount){
                max = totalWinCount;
                index = i;
            }
        }
        result = A.get(index);
        
        return result;
    }

}