[프로그래머스 258709] 주사위 고르기

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

프로그래머스

 

A, B 플레이어가 주사위를 절반으로 나누고, 본인의 주사위에서 나오는 숫자들의 합이 최대이면 승리하는 게임을 함.

이 때 A가 승리하는 확률이 최대이도록 하는 A의 주사위 배열을 구해야 함

 

 

일단 주사위의 개수는 최대 10, 주사위에 적힌 숫자도 최대 100이므로 완전탐색 을 느껴야 한다

완탐으로 구현될 코드의 흐름을 단계별로 생각해 보면

 

1. 주사위의 조합을 구한다

2. 해당 주사위의 조합에서 나올 수 있는 합들을 구한다

3. A, B의 각 합을 비교하여 A의 최적의 주사위 조합을 구한다

 

 

여기에서 

조합은 재귀 방식으로 구하여 (select func)

이 함수의 최대 depth에서 구한 조합에서 나올 수 있는 합들의 리스트를 만들고 승리 확률을 계산했다 (calVictories func)

A, B의 조합으로 구한 각각의 합 리스트에서 A 리스트를 순회하면서(aResult) 각 원소보다 작은 원소가 B 리스트(bResult)에 몇 개나 존재하는지 binary search를 활용한 lowerbound 함수를 통하여 계산함.(*밑에 참고)

A와 B의 주사위 조합은 서로 대칭되니까 이를 활용해서 더 효율적인 코드를 만들수 있을 것 같긴한데.. 하진 않았다

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.stream.IntStream;

class Solution {

    int n;
    boolean[] maxSelected;
    int maxVictories = 0;
    int[][] diceArr;
    public int[] solution(int[][] dice) {

        n = dice.length;
        boolean[] selected = new boolean[n];
        diceArr = dice;
        for(int i=0; i<n; i++){
            selected[i] = true;
            select(selected, i, 1);
            selected[i] = false;
        }

        int[] answer = IntStream.range(0, maxSelected.length).filter(i -> maxSelected[i]).map(i-> i+1).toArray();
        return answer;
    }

    private void select(boolean[] selectedA, int currSelected, int depth){
        if(depth == n/2) {    //경우의 수 cal
            int currVictories = calVictories(selectedA);
            if(currVictories > maxVictories){
               maxVictories = currVictories;
               maxSelected = selectedA.clone();
            }
            return;
        }

        //위치
        for(int i=currSelected+1; i<n; i++){
            selectedA[i] = true;
            select(selectedA, i, depth + 1);
            selectedA[i] = false;
        }
    }

    //승리 확률 계산
    private int calVictories(boolean[] selected){

        int[] aDice = IntStream.range(0, selected.length).filter(i -> selected[i]).toArray();
        int[] bDice = IntStream.range(0, selected.length).filter(i -> !selected[i]).toArray();

        ArrayList<Integer> aResult = new ArrayList<>(), bResult = new ArrayList<>();

        int victories = 0;
        cal(aResult, aDice, 0, 0);
        cal(bResult, bDice, 0, 0);
        Collections.sort(aResult);  Collections.sort(bResult);
        for(int i=0; i<aResult.size(); i++){
            victories += lowerbound(bResult, aResult.get(i));
        }
        return victories;
    }

    //가능한 모든 sum -> list 저장
    private void cal(ArrayList<Integer> result, int[] dice, int currDiceIdx, int currSum){
        if(currDiceIdx == n/2){
            result.add(currSum);
            return;
        }

        int[] currDice = diceArr[dice[currDiceIdx]];
        for(Integer num : currDice){
            cal(result, dice, currDiceIdx+1, currSum + num);
        }
    }

    private int lowerbound(ArrayList<Integer> list, int value){
        int result = Collections.binarySearch(list, value);       
        if(result < 0) {
            return -(result + 1);
        }else{
            while(result > 0 && list.get(result-1).equals(value)){
                result--;
            }
            return result;
        }
    }
}