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

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

접근

A와 B가 있다. 먼저, n개의 주사위 중 $\frac{n}{2} $ 개를 선택하는 조합을 구해야 한다.

그리고 각 주사위 조합에 대해 주사위 점수 합산을 계산하여 저장한다.

마지막으로, A 주사위 조합 중 점수 합산에서 가장 큰 승률을 가진 조합을 찾아 반환한다.

이 문제는 총 세 문제로 구분할 수 있다.

첫 번째, 주사위 조합을 구하는 문제는 생각보다 쉽게 구현할 수 있다.

재귀를 사용하여 조합을 구현하면 된다. 나의 경우에는 주사위를 선택하는 경우와 선택하지 않는 경우로 구분하여 모든 조합을 구했다.

두 번째, 주사위 점수 합산을 계산하는 문제는 합산만 저장하는 게 아니라 그 합산이 어떤 주사위 조합을 가리키는지까지 저장해야 한다.

합산만 저장하면 나중에 가장 큰 승률의 주사위 조합이 무엇인지 알 수 없다. 나의 경우에는 Map에 키로 주사위 조합의 인덱스를, 값으로 합산을 저장했다.

세 번째, 합산에서 가장 큰 승률의 주사위 조합을 구하는 문제는 성능을 고려해봐야 한다.

dice[i] 의 길이가 6이고 dice 의 길이가 $2\leq{...}\leq{10} $ 이기 때문에 첫 번째, 두 번째 문제에서는 성능을 크게 고려할 부분이 없다.

하지만, 세 번째 문제는 두 번째 문제에서 구한 각 주사위별 합산의 길이가 최대 ${}_{10}C_5\times{6^5} $ 이기 때문에 두 주사위에 대해 이중 탐색으로 최대 승률을 구하게 되면 총 연산횟수가 $({}_{10}C_5)^2\times{6^{5}}=4,444,263,936 $이 되므로 시간 제한에 걸리게 된다.

따라서, 이분 탐색을 사용하여 문제를 해결하겠다. 이분 탐색을 사용하면 총 연산횟수가 $\log{({}_{10}C_5\times{6^5})}\times{{}_{10}C_5}=5,118 $이 되므로 주어진 시간 제한을 만족할 수 있다.

주의할 점은 이분 탐색을 사용하여 승리 횟수를 구할 때 $O(1) $ 이나 $O(N) $ 의 시간복잡도로 접근해야 한다는 것이다.

이는 이분 탐색 중 mid 를 통해 논리적으로 승리 횟수를 $O(1) $ 의 시간 복잡도로 구할 수 있다.

참고로, 오름차순 정렬에 의해 총 연산횟수는 $\log{({}_{10}C_5\times{6^5})}\times{{}_{10}C_5}\times{6^5}=39,793,680 $ 이 된다.

소스코드(Java)

import java.util.*;
import java.util.stream.*;

class Solution {

    int[][] gDice;

    List<List<Integer>> idxsA = new ArrayList<List<Integer>>();
    List<List<Integer>> idxsB = new ArrayList<List<Integer>>();
    Map<Integer, List<Integer>> sumsA = new HashMap<>();
    Map<Integer, List<Integer>> sumsB = new HashMap<>();


    void comb(List<Integer> idxs, int cnt) {
        if(idxs.size() == gDice.length/2) {
            idxsA.add(new ArrayList<>(idxs));
            return;
        }
        if(cnt == gDice.length) return;

        idxs.add(cnt);
        comb(idxs, cnt+1);
        idxs.remove(idxs.size()-1);
        comb(idxs, cnt+1);
    }

    void sumA(int idx, int cnt, int sum) {
        if(cnt == idxsA.get(idx).size()) {
            List<Integer> temp = sumsA.getOrDefault(idx, new ArrayList<Integer>());
            temp.add(sum);
            sumsA.put(idx, temp);
            return;
        }
        for(int i = 0; i < gDice[idxsA.get(idx).get(cnt)].length; i++) {
            sumA(idx, cnt + 1, sum + gDice[idxsA.get(idx).get(cnt)][i]);
        }
    }

    void sumB(int idx, int cnt, int sum) {
        if(cnt == idxsB.get(idx).size()) {
            List<Integer> temp = sumsB.getOrDefault(idx, new ArrayList<Integer>());
            temp.add(sum);
            sumsB.put(idx, temp);
            return;
        }
        for(int i = 0; i < gDice[idxsB.get(idx).get(cnt)].length; i++) {
            sumB(idx, cnt + 1, sum + gDice[idxsB.get(idx).get(cnt)][i]);
        }
    }

    int[] binarySearch() {

        int max = -1;
        int[] result = new int[gDice.length/2];

        for(int i = 0; i < idxsA.size(); i++) {
            List<Integer> listA = sumsA.get(i);
            List<Integer> listB = sumsB.get(i);

            int winCount = 0;

            for(int va : listA) {
                int start = 0;
                int end = listB.size()-1;
                int mid = (start+end) / 2;

                while(start <= end) {
                    if(listB.get(mid) >= va) {
                        end = mid - 1;
                    } else {
                        start = mid + 1;
                    }
                    mid = (start+end) / 2;
                }
                winCount += mid + 1;
            }
            if(max < winCount) {
                max = winCount;
                result = idxsA.get(i).stream().map(v -> v+1).mapToInt(Integer::intValue).toArray();
            }
        }
        return result;
    }

    public int[] solution(int[][] dice) {

        gDice = dice;

        //A의 주사위 결정
        comb(new ArrayList<>(), 0);

        //B의 주사위 결정
        for(int i = 0; i < idxsA.size(); i++) {
            List<Integer> temp = new ArrayList<>();
            for(int j = 0; j < dice.length; j++) {
                if(!idxsA.get(i).contains(j)) temp.add(j);
            }
            idxsB.add(temp);
        }

        //A 주사위에 대한 합산 계산
        for(int i = 0; i < idxsA.size(); i++) {
            sumA(i, 0, 0);
        }

        //B 주사위에 대한 합산 계산
        for(int i = 0; i < idxsB.size(); i++) {
            sumB(i, 0, 0);
        }

        //이분 탐색 전 A, B 주사위에 대한 합산 결과 오름차순으로 정렬
        for(int key : sumsA.keySet()) {
            sumsA.put(key, sumsA.get(key).stream().sorted().collect(Collectors.toList()));
        }

        for(int key : sumsB.keySet()) {
            sumsB.put(key, sumsB.get(key).stream().sorted().collect(Collectors.toList()));
        }

        //이분 탐색
        return binarySearch();
    }
}

 

테스트 성공

이 문제의 가장 힘든 점은 구현이었다.

나는 두 번째 문제와, 세 번째 문제에서 구현의 어려움을 겪었다.

두 번째 문제에서는 아직 재귀가 익숙하지 않아 겪은 문제였고,

세 번째 문제에서는 mid를 이용하여 논리적으로 winCount를 계산하는 부분에서 겪은 문제였다.

세 번째 문제는 주어진 문제를 해결하면서 겪는 당연한 문제지만 두 번째 문제는 그렇지 않기에, 연습을 통해 재귀에 익숙해지도록 노력을 해야 한다.