[Programmers] Lv3 주사위 고르기

주사위 고르기

문제 해설

이 문제는 Lv3 급 문제에서 몇년 전부터 자주 보이기 시작한 두개 이상의 알고리즘이 사용되는 문제 유형 중 하나이다. 조합과 이분 탐색이 사용된 문제로 이분 탐색은 효율성을 위해 사용한다.

문제의 조건을 살펴보면 아래와 같다

1. n 은 2의 배수이다.
2. 6개의 면에 숫자가 적힌 n개의 주사위가 주어진다.
3. 두 명의 플레이어 A, B는 각 n/2 개의 주사위를 가져간다.
4. 각 플레이어는 가져간 주사위를 굴려 나온 숫자들의 합을 상대방과 비교하여 승/무/패를 가린다.
5. 이 조건에 따라 가장 많은 승리할 수 있는 주사위 조합을 선택하라.

문제가 길게 적혀있지만 핵심은 위 다섯 가지로 요약 가능하다. 무승부를 제외한 승률을 구하는 문제가 아니기 때문에 승률이 아닌 승리하는 경우의 수만 구하면 문제를 해결 할 수 있다.

해결 순서

DFS를 이용하여 주사위를 고르는 모든 조합의 수를 구하는 함수를 작성한다.
DFS를 이용하여 주어진 주사위 조합으로 각 플레이어가 낼 수 있는 모든 점수의 조합을 구하는 함수를 작성한다.
플레이어 A와 플레이어 B의 점수를 2에서 구한 함수로 모두 구한다.
플레이어 B의 점수 조합(BScore) 을 오름차순 정렬한다.
플레이어 A의 점수 조합 중 하나를 선택하여 BScore에 이분 탐색을 진행, 승리 수를 반환한다.
플레이어 A의 모든 점수에 대해 5를 반복하여 총 승리 수를 구한다.
5와 6을 A의 모든 주사위 조합에 대해 진행한다.
최대 승리 수에 해당하는 인덱스를 반환한다.

Code

import java.util.*;

class Solution {

    private int[][] dice;
    private int[] comb;
    private int limit;
    private int[] answer;
    private List<int[]> diceCombs = new ArrayList<>();

    private int countWins(int target, List<Integer> scores) {
        int left = 0;
        int right = scores.size() - 1;
        int mid = 0;

        while(left <= right) {
            mid = (left + right) / 2;
            int value = scores.get(mid);

            if(value < target) { // 현재 값이 검색하려는 값보다 작다면
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private void makeScoreCombination(int[] indices, int start, int limit, int score, List<Integer> output) {
        if(start == limit) {
            output.add(score);
            return;
        }

        for(int i = 0 ; i < 6 ; i++) {
            makeScoreCombination(indices, start + 1, limit, score + dice[indices[start]][i], output);
        }
    }

    private void makeCombination(int start, int cur, int limit) {
        if(cur == limit) {
            diceCombs.add(Arrays.stream(comb).toArray());
            return;
        }

        for(int i = start ; i < dice.length ; i++) {
            comb[cur] = i;
            makeCombination(i + 1, cur + 1, limit);
        }
    }

    public int[] solution(int[][] dice) {
        this.dice = dice;
        limit = dice.length;
        answer = new int[limit / 2];
        comb = new int[limit / 2];
        makeCombination(0, 0, limit/2);

        int maxWin = 0;

        // System.out.println("Score result ");
        for(int i = 0 ; i < diceCombs.size() / 2 ; i++) {

            int[] aDices = diceCombs.get(i);
            int[] bDices = diceCombs.get(diceCombs.size() - i - 1);

            List<Integer> aScore = new ArrayList<>();
            List<Integer> bScore = new ArrayList<>();

            makeScoreCombination(aDices, 0, limit/2, 0, aScore);
            makeScoreCombination(bDices, 0, limit/2, 0, bScore);

            Collections.sort(aScore);
            Collections.sort(bScore);

            int aTotalWin = 0; // 승률은 중요하지 않다. 어차피 모두 같은 시행 회수이므로 승리 수만 합계하여 비교하면 된다.
            int bTotalWin = 0; // 승률은 중요하지 않다. 어차피 모두 같은 시행 회수이므로 승리 수만 합계하여 비교하면 된다.
            
            for(int aValue : aScore) {
                int winCount = countWins(aValue, bScore);
                aTotalWin+=winCount;
            }
            
            for(int bValue : bScore) {
                int winCount = countWins(bValue, aScore);
                bTotalWin += winCount;
            }
            

            if(aTotalWin > maxWin) {
                maxWin = aTotalWin;
                for(int dIdx = 0 ; dIdx < limit/2 ; dIdx++) {
                    answer[dIdx] = aDices[dIdx] + 1;
                }
            }
            
            if(bTotalWin > maxWin) {
                maxWin = bTotalWin;
                for(int dIdx = 0 ; dIdx < limit/2 ; dIdx++) {
                    answer[dIdx] = bDices[dIdx] + 1;
                }
            }
        }

        return answer;
    }
}

주의점

이분 탐색 문제에서 항상 주의해야하는 탐색 범위의 축소 방법과, 탐색 종료 조건을 신경 써야한다. 이 문제는 Lower Bound 를 구하는 문제 유형이기 때문에 위 코드와 같이 종료 조건을 지정해야 한다.