240325 주사위 고르기

private ArrayList<Combination> combinations;
private int n;

private class Combination {
	Integer[] selected;
	HashMap<Integer, Integer> sums;

	Combination(Integer[] selected) {
		this.selected = selected;
		sums = new HashMap<>();
	}

	Combination() {
		selected = new Integer[0];
		sums = new HashMap<>();
	}

	void setSum(int[][] dice) {
		ArrayList<Integer> sumsList = new ArrayList<>();
		for (int i : dice[selected[0] - 1]) {
			sumsList.add(i);
		}
		for (int i = 1; i < selected.length; i++) {
			ArrayList<Integer> temp = new ArrayList<>();
			for (Integer p : sumsList) {
				for (int n : dice[selected[i] - 1]) {
					temp.add(p + n);
				}
				sumsList = temp;
			}
		}
		for (Integer num : sumsList) {
			sums.put(num, sums.getOrDefault(num, 0) + 1);
		}
	}

	boolean isOpposite(Combination other) {
		Integer[] o = other.selected;
		for (int i = 0; i < o.length; i++) {
			for (int j = 0; j < o.length; j++) {
				if (selected[i] == o[j]) {
					return false;
				}
			}
		}
		return true;
	}
}

private void findCombinations(Integer[] combination) {
	int prev = 0;
	int idx = 0;
	for (Integer i : combination) {
		if (i == null) {
			break;
		}
		prev = i;
		idx++;
	}
	if (idx == combination.length) {
		combinations.add(new Combination(combination));
		return;
	}
	for (int i = prev + 1; i <= n; i++) {
		Integer[] temp = combination.clone();
		temp[idx] = i;
		findCombinations(temp);
	}
}

private int calculateScore(int idx) {
	int score = 0;
	Combination a = combinations.get(idx);
	Combination b = new Combination();
	for (Combination combination : combinations) {
		if (a.isOpposite(combination)) {
			b = combination;
			break;
		}
	}
	for (Entry<Integer, Integer> aEntry : a.sums.entrySet()) {
		int aNum = aEntry.getKey();
		int aCount = aEntry.getValue();
		for (Entry<Integer, Integer> bEntry : b.sums.entrySet()) {
			int bNum = bEntry.getKey();
			int bCount = bEntry.getValue();
			if (aNum > bNum) {
				score += aCount * bCount;
			}
		}
	}
	return score;
}

public int[] solution(int[][] dice) {
	combinations = new ArrayList<>();
	n = dice.length;
	int[] result;
	findCombinations(new Integer[n / 2]);
	for (Combination c : combinations) {
		c.setSum(dice);
	}
	result = new int[combinations.size()];
	for (int i = 0; i < result.length; i++) {
		result[i] = calculateScore(i);
	}
	int idx = 0;
	int max = 0;
	for (int i = 0; i < result.length; i++) {
		if (result[i] > max) {
			idx = i;
			max = result[i];
		}
	}
	int[] answer = new int[n / 2];
	for (int i = 0; i < answer.length; i++) {
		answer[i] = combinations.get(idx).selected[i];
	}
	return answer;
}

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