marinesnow34
0%

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

작성일 In

주사위 고르기 (Lv. 3)

문제를 간단하게 요약하면 다음과 같습니다.

  • 요약

    1. A, B가 n개의 주사위를 가지고 승부
    2. 주사위에는 6개의 면이 있고 각 면이 나올 확률 동일
    3. 서로 중복 없이 n/2개의 주사위를 골라서 승부
    4. 가져간 주사위를 모두 굴려 나온 눈의 합이 큰 사람이 승리
    5. A가 승리할 확률이 가장 높은 주사위의 조합을 구하라

  • 제한 조건

    1. 2 <= dice.length == n <= 10 (n은 2의 배수)
    2. 1 <= dice[i].length <= 6

테스트 케이스

주사위 구성
#1 [1, 2, 3, 4, 5, 6]
#2 [3, 3, 3, 3, 4, 4]
#3 [1, 3, 3, 4, 4, 4]
#4 [1, 1, 4, 4, 5, 5]
A의 주사위 승 무 패
#1, #2 596 196 504
#1, #3 560 176 560
#1, #4 616 184 496
#2, #3 496 184 616
#2, #4 560 176 560
#3, #4 504 196 596

A가 승리할 확률이 가장 높은 주사위의 조합은 #1, #4 입니다.

해설

주사위는 제한 조건을 제외하고는 어떠한 규칙을 찾을 수 없습니다. 또한 주사위의 최대 개수가 10개이므로 완전 탐색으로 해결할 수 있을거 같습니다. 시간 복잡도를 계산해서 완전 탐색으로 해결할 수 있는지 확인해보겠습니다.

시간 복잡도를 확인하기 전에 테스크를 나누고 각 테스크의 시간 복잡도를 계산해보겠습니다. 테스크를 크게 2개로 나누어야 합니다.

  1. A가 가질 수 있는 주사위의 조합 구하기
  2. 가져간 주사위를 굴려서 나올 수 있는 결과 구하기

A가 가질 수 있는 주사위의 조합 구하기

A가 가질 수 있는 주사위의 조합을 구하기 위해서는 Combination을 사용해야 합니다. n이 최대 10이므로 주사위 10개 중에 5개를 고르는 경우의 수는 252입니다.

저는 백트래킹을 활용해서 조합을 구했습니다.

1
2
3
4
5
6
7
8
9
10
11
public void combination(int n, int k, int[][] dice){
    if(n == N/2){
        // 2번 과정
        return;
    }
    for(int i = k; i < N; i++){
        visit[i] = true;
        combination(n+1, i+1, dice);
        visit[i] = false;
    }
}

n은 현재까지 고른 주사위의 개수이고 k는 현재 고를 수 있는 주사위의 시작 인덱스입니다. k를 사용한 이유는 조합에서는 중복을 허용하지 않기 때문에 다음 주사위를 고를 때 현재 고른 주사위의 다음 인덱스부터 고를 수 있도록 했습니다.

visit을 사용해서 현재 고른 주사위를 표시했습니다.

가져간 주사위를 굴려서 나올 수 있는 결과 구하기

시간 복잡도 미고려

A, B가 가져간 주사위 조합마다 모두 굴려서 나올 수 있는 결과를 구해야 합니다. 그런 다음 A가 이기는 경우의 수를 구해야 합니다. 만일 모든 경우의 수를 구한다면, 주사위 면의 수가 6이므로 O(6^N)가 됩니다. N은 최대 10이므로 6^10 = 60,466,176 입니다. 하지만 주사위의 조합과 함께 고려한다면 60,466,176 * 252 = 15,237,476,352로 시간 초과가 발생 합니다.

시간 복잡도 고려

시간 복잡도를 줄이기 위해서 나올 수 있는 결과를 A, B를 함께 고려하지 않고 A, B 따로 구합니다. 그렇게 되면 A결과 합 중복 조합과 B결과 합 중복 조합을 따로 구하게 됩니다. 그러고 나서 A의 각 합을 이분탐색을 활용해서 B의 결과 보다 큰 경우의 수의 합을 구하면 그게 A가 이기는 경우의 수가 됩니다.

시간 복잡도는 O(NlogN)으로 N은 n이 최대 10일 때 6^5 = 7,776으로 시간 초과가 발생하지 않습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public void expectGame(int[][] dice){
    aDice = new int[N/2];
    bDice = new int[N/2];
    int aSize = 0, bSize = 0;
    
    //visit에서 구한 A, B의 주사위 조합을 aDice, bDice 배열에 담아줍니다.
    for(int i = 0; i < N; i++){
        if(visit[i]) aDice[aSize++] = i;
        else bDice[bSize++] = i;
    }

    // A, B의 주사위 결과의 합을 담을 리스트
    aSumCombi = new ArrayList<>(10000);
    bSumCombi = new ArrayList<>(10000);

    // A,B의 주사위 결과의 합을 따로 구합니다.
    rollDice(0, 0, aDice, dice, aSumCombi);
    rollDice(0, 0, bDice, dice, bSumCombi);
    
    // A가 이기는 경우의 수를 구합니다.
    game(aSumCombi, bSumCombi);
    return;
}
public void rollDice(int n, int sum, int[] nowDice, int[][] dice, List<Integer> sumCombi){
    if(n == N/2){
        //합을 리스트에 담습니다.
        sumCombi.add(sum);
        return;
    }
    for(int i = 0; i < 6; i++){
        rollDice(n+1, sum + dice[nowDice[n]][i], nowDice, dice, sumCombi);
    }
}
public void game(List<Integer> aSumCombi, List<Integer> bSumCombi){
    // 이분 탐색을 위해 정렬합니다.
    Collections.sort(bSumCombi);
    // A의 합보다 작은 B의 합의 개수를 구해서 aWin에 더합니다.
    for(Integer i : aSumCombi){
        aWin = aWin + lowerBound(bSumCombi, i);
    }
}
// 이분 탐색
public int lowerBound(List<Integer> arr, int t){
    int s = 0;
    int e = arr.size();
    while(s < e){
        Integer mid = (s+e) / 2;
        if(arr.get(mid) < t) s = mid + 1;
        else e = mid;
    }
    return e;
}

후기

백트래킹과 이분탐색을 적절히 조합하면 문제를 해결할 수 있습니다. 어려운 알고리즘은 아니지만 구현 난이도가 조금 있고, 시간 복잡도를 고려하지 않았더라면 시간 초과가 발생할 수 있습니다. 항상 코드를 작성하기 전에 시간 복잡도를 고려하는 습관을 들이는 것이 중요합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.*;

class Solution {
    // A, B n개의 주사위
    // 6개 면에 1~n
    int N, win, aWin;
    int[] sol, battleDice, aDice, bDice;
    List<Integer> aSumCombi, bSumCombi;
    boolean[] visit = new boolean[15];
    
    public int lowerBound(List<Integer> arr, int t){
        int s = 0;
        int e = arr.size();
        while(s < e){
            Integer mid = (s+e) / 2;
            if(arr.get(mid) < t) s = mid + 1;
            else e = mid;
        }
        return e;
    }
    
    public void game(List<Integer> aSumCombi, List<Integer> bSumCombi){
        Collections.sort(bSumCombi);
        for(Integer i : aSumCombi){
            aWin = aWin + lowerBound(bSumCombi, i);
        }
    }
    
    public void rollDice(int n, int sum, int[] nowDice, int[][] dice, List<Integer> sumCombi){
        if(n == N/2){
            sumCombi.add(sum);
            return;
        }
        for(int i = 0; i < 6; i++){
            rollDice(n+1, sum + dice[nowDice[n]][i], nowDice, dice, sumCombi);
        }
    }
    
    public void expectGame(int[][] dice){
        aDice = new int[N/2];
        bDice = new int[N/2];
        int aSize = 0, bSize = 0;
        
        for(int i = 0; i < N; i++){
            if(visit[i]) aDice[aSize++] = i;
            else bDice[bSize++] = i;
        }

        aSumCombi = new ArrayList<>(10000);
        bSumCombi = new ArrayList<>(10000);
        
        rollDice(0, 0, aDice, dice, aSumCombi);
        rollDice(0, 0, bDice, dice, bSumCombi);
        
        game(aSumCombi, bSumCombi);
        
        return;
    }
    
    public void combination(int n, int k, int[][] dice){
        if(n == N/2){
            aWin = 0;
            expectGame(dice);
            if(aWin > win){
                for(int i = 0; i < N/2; i++) sol[i] = aDice[i] + 1;
                win = aWin;
            }
            return;
        }
        for(int i = k; i < N; i++){
            visit[i] = true;
            combination(n+1, i+1, dice);
            visit[i] = false;
        }
    }
    public int[] solution(int[][] dice) {
        N = dice.length;
        battleDice = new int[N];
        sol = new int[N/2];
        combination(0, 0, dice);
        return sol;
    }
}