프로그래머스 Java Lv3 주사위 고르기

 

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

 

해당 문제는 다음 2가지 포인트만 잘 생각하면 풀 수 있는 문제이다.

 

1. 모든 주사위 조합을 구하고, A 와 B의 경우를 매칭하는 것

2. 주사위 조합에 따라 나올 수 있는 점수 조합의 수를 구하고 압축하는 것

 

문제에서 주어진 n개의 주사위 중 절반의 주사위를 가져갈 때 승리할 확률이 가장 높도록 주사위를 선택해야한다.

그러므로 우선 생각해야할 것은 나올 수 있는 주사위 조합의 경우이다.

 

주어진 조건에 따르면 주사위의 수 n은 2 ~ 10 사이의 짝수 이다.

 

n = 2 인 경우, 주사위 [ 1, 2 ] 가 있다면 다음과 같은 경우가 존재한다.

1. 주사위 "1" 을 고른 경우

2. 주사위 "2" 를 고른 경우

 

n = 4 인 경우, 주사위 [ 1, 2, 3, 4 ] 가 있다면 다음과 같은 경우가 존재한다.

1. 주사위 "1, 2" 을 고른 경우

2. 주사위 "1, 3" 을 고른 경우

3. 주사위 "1, 4" 을 고른 경우

4. 주사위 "2, 3" 을 고른 경우

5. 주사위 "2, 4" 을 고른 경우

6. 주사위 "3, 4" 을 고른 경우

 

다음과 같이 모든 조합의 수를 순서대로 구해보면 한 가지 규칙이 눈에 보일 것 이다.

A가 "1, 2"를 골랐다면 B는 "3, 4"를 골랐을 것이다.

A가 "1, 3"를 골랐다면 B는 "2, 4"를 골랐을 것이다.

A가 "1, 4"를 골랐다면 B는 "2, 3"를 골랐을 것이다.

이를 위의 조합의 순서와 비교해보면 다음과 같이 연결되는 것을 알 수 있다.

1번과 6번 /  2번과 5번 / 3번과 4번

 

 

이제 각 주사위 조합과 그 상대를 매칭하는 것은 구하였으니

각 주사위 조합에서의 점수를 구하고, 가장 많이 이기는 조합을 선택하면 된다.

 

여기서 필요한 것이 "점수 조합의 수를 구하고 압축하는 것"이다.

아마 점수 조합의 수를 구하는 것에는 이견이 없겠지만 "압축하는 것"에는 의문을 품을 수 있다. 왜 필요한 것일까?

 

이를 이해하기 위해 n = 10 인 경우를 생각해보자.

주사위는 6개의 면을 가지고, 각 조합마다 5개의 주사위가 있으니 6 ^ 5 = 7,776 개의 점수 조합이 나올 것 이다.

각 주사위 조합에 따른 점수의 조합마다 승부를 겨루어야 하니 7,776 * 7,776 = 60,466,176 번의 비교가 필요하다.

 

주사위 조합의 수는 10개의 주사위 중 순서에 상관없이 5개를 선택하는 것이니, 10 C 5 = 252개의 조합이 나오고,

각 조합을 A와 B로 매칭 시키면 252 / 2 = 151 번의 승부가 나올 것이다.

 

즉, 모든 조합을 구하고 모두 하나씩 비교한다면 최대 151 * 60,466,176 = 9,130,392,576 의 연산이 필요하다. ( 약 91억 )

 

이는 매우 비효율 적이다. 점수 조합에는 중복된 점수들이 존재할 것이다. 중복된 점수를 압축해서 표현하면 어떨까?

예를 들어 [ 1 1 1 1 1 2 2 2 2 2 ], [ 1 1 1 1 1 3 3 3 3 3 ] 다음과 같은 2개의 점수 조합을 비교한다고 생각하자.

10 * 10 = 100 번의 비교가 필요하다.

 

하지만 [ 1점-5개, 2점-5개 ] , [ 1점-5개, 3점-5개 ] 로 표현한다면

2 * 2 = 4번의 비교면 충분하다. 비교 연산의 수를 획기적으로 줄일 수 있는 것이다.

 

아이디어는 다 생각하였다. 그렇다면 이를 코드로 어떻게 표현할 수 있을까?

 

우선 모든 주사위 조합은 재귀를 통해 구하였다. 주사위 조합은 정수형 배열 int[] combi에 표현하고 각 조합이 구해지면

deepCopy를 한 뒤에 ArrayList 에 저장한다.

 

점수 조합의 수 압축을 위해서 필자는 Java의 HashMap을 사용했다.

key 값으로 점수를 사용하고, value 값으로 각 점수의 수를 사용하였다.

 

 

 

 

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class Solution {

    private int[][] dice;
    private int[] combi;
    private ArrayList<int[]> diceCombination;
    private ArrayList<Integer> score;

    public int[] solution(int[][] dice) {
        int[] answer = {};
        int diceCnt = dice.length;
        int maxWinCnt = 0;

        this.dice = dice;
        this.diceCombination = new ArrayList<>();
        this.score = new ArrayList<>();

        combi = new int[diceCnt / 2];
       //모든 점수 조합 구하기
        calculateCombination(0, 0, diceCnt / 2);

        for (int i = 0; i < diceCombination.size() / 2; i++) {
            int myIdx = i;
            int oppIdx = diceCombination.size() - i - 1;

            int[] myCombination = diceCombination.get(myIdx);
            int[] oppCombination = diceCombination.get(oppIdx);

		//점수 조합 압축
            HashMap<Integer, Integer> myScoreCnt = calculateScoreCnt(myCombination, 0, diceCnt / 2);
            HashMap<Integer, Integer> oppScoreCnt = calculateScoreCnt(oppCombination, 0, diceCnt / 2);

            int winCnt = 0;
            int loseCnt = 0;
            for (int m : myScoreCnt.keySet()) {
                for (int o : oppScoreCnt.keySet()) {
                    if (m > o) {
                        winCnt += (myScoreCnt.get(m) * oppScoreCnt.get(o));
                    } else if (m < o) {
                        loseCnt += (myScoreCnt.get(m) * oppScoreCnt.get(o));
                    }
                }
            }
            if (maxWinCnt < winCnt) {
                maxWinCnt = winCnt;
                answer = myCombination;
            }
            if (maxWinCnt < loseCnt) {
                maxWinCnt = loseCnt;
                answer = oppCombination;
            }
        }
        // index 0 주사위 > 1번 주사위 변경 작업
        for (int i = 0; i < answer.length; i++) {
            answer[i]++;
        }
        return answer;
    }

    private void calculateCombination(int start, int curDepth, int maxDepth) {
        if (curDepth == maxDepth) {
            diceCombination.add(arrayDeepCopy(combi));
            return;
        }
        for (int i = start; i < dice.length; i++) {
            combi[curDepth] = i;
            calculateCombination(i + 1, curDepth + 1, maxDepth);
        }
    }

    private int[] arrayDeepCopy(int[] arr) {
        return Arrays.stream(arr).toArray();
    }

    private HashMap<Integer, Integer> calculateScoreCnt(int[] combi, int curDepth, int maxDepth) {
        if (curDepth == maxDepth) {
            HashMap<Integer, Integer> scoreCnt = new HashMap<>();
            for (int s : score) {
                if (!scoreCnt.containsKey(s)) {
                    scoreCnt.put(s, 1);
                } else {
                    scoreCnt.put(s, scoreCnt.get(s) + 1);
                }
            }
            score.clear();
            return scoreCnt;
        }
        int idx = combi[curDepth];
        if (score.size() == 0) {
            for (int i = 0; i < 6; i++) {
                score.add(dice[idx][i]);
            }
        } else {
            int size = score.size();
            for (int i = 0; i < size; i++) {
                int s = score.remove(0);
                for (int j = 0; j < 6; j++) {
                    score.add(dice[idx][j] + s);
                }
            }
        }
        return calculateScoreCnt(combi, curDepth + 1, maxDepth);
    }
}