[Programmers] 주사위 고르기 (Java)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/258709

프로그래머스

문제 풀이

dice[]:주사위 정보가 주어졌을 때 A와 B가 주사위를 반반가질 때, A가 이길 확률이 높은 주사위 번호를 오름차순으로 1차원 배열로 return

 

1. 우선 A, B가 주사위를 가지는 경우의 수를 조합으로 구해준다. 이 중에서도 1번 주사위는 무조건 A가 가지게 되어도 모든 경우의 수를 구할 수 있기 때문에 1번 주사위는 제외하고 나눠준다. (시간을 조금이라도 줄이기 위해)

2. 나눈 주사위의 전체 합을 순열로 1차원 배열로 저장한다. (크기는 6^각 팀이 가진 주사위의 수)

3. 정렬을 하고 각 팀이 이긴 횟수를 저장한다. 정렬을 했기 때문에 진다면 break문을 통해 빠져나간다.

4. 1에서 A가 무조건 1번 주사위를 가지게 했지만 2, 3번 주사위의 승률이 높을 경우도 있기 때문에 모든 경우의 수의 이긴 횟수로 max값을 저장해준다.

5. max이 갱신되면 팀이 저장된 visited를 answer[]에 저장한다.

 

코드

import java.util.*;

class Solution {
    
    int[] answer;
    int DICE_DIR = 6;
    int diceNum = 0;
    int maxWin = 0;
    
    public int[] solution(int[][] dice) {
        
        // init
        diceNum = dice.length;
        boolean[] visited = new boolean[diceNum];
        visited[0] = true;
        answer = new int[diceNum / 2];
        
        // 주사위를 나눠가지는 경우의 수
        combination(1, 0, visited, dice);
        
        
        return answer;
    }
    
    public void combination(int idx, int cnt, boolean[] visited, int[][] dice) {
        if(cnt == diceNum / 2 - 1) {
            // 각 주사위의 합
            int[] AScore = getSumDiceScore(true, visited, dice);
            int[] BScore = getSumDiceScore(false, visited, dice);
            
            // 정렬
            Arrays.sort(AScore);
            Arrays.sort(BScore);
            
            // 이긴 횟수 count
            int AwinCount = getWinCount(AScore, BScore);
            int BwinCount = getWinCount(BScore, AScore);
            
            // A가 이겼을 경우
            int answerIdx = 0;
            if(maxWin < AwinCount) {
                maxWin = AwinCount;
                for(int i=0; i<visited.length; i++) {
                    if(visited[i]) answer[answerIdx++] = i + 1;
                }
            }
            
            // B가 이겼을 경우
            answerIdx = 0;
            if(maxWin < BwinCount) {
                maxWin = BwinCount;
                for(int i=0; i<visited.length; i++) {
                    if(!visited[i]) answer[answerIdx++] = i + 1;
                }
            }
            
            return;
        }
        
        for(int i=idx; i<visited.length; i++) {
            if(!visited[i]) {
                visited[i] = true;
                combination(i+1, cnt+1, visited, dice);
                visited[i] = false;
            }
        }
    }
    
    public int getWinCount(int[] score1, int[] score2) {
        int winCount = 0;
        
        for(int i=0; i<score1.length; i++) {
            for(int j=0; j<score2.length; j++) {
                if(score1[i] > score2[j]) {
                    winCount++;
                } else break;
            }
        }
        
        return winCount;
    }
    
    public int[] getSumDiceScore(boolean team, boolean[] visited, int[][] dice) {
        int[] arr = new int[(int) Math.pow(DICE_DIR, diceNum/2)];
        int[] select = new int[diceNum / 2];
        int index = 0;
        idx = 0;
        
        for(int i=0; i<diceNum; i++) {
            if(visited[i] == team) {
                select[index++] = i;
            }
        }
        
        // 나눠가진 주사위의 합
        permutation(0, arr, select, 0, dice);
        
        return arr;
    }
    
    int idx;
    public void permutation(int cnt, int[] arr, int[] select, int sum, int[][] dice) {
        if(cnt == diceNum/2) {
            arr[idx++] = sum;
            return;
        }
        
        for(int i=0; i<DICE_DIR; i++) {
            permutation(cnt+1, arr, select, sum + dice[select[cnt]][i], dice);
        }
    }
}