Post

주사위 고르기

Posted
By SON YOUSANG
19 min read

출처 프로그래머스

문제 설명

A와 B가 n개의 주사위를 가지고 승부를 합니다.

주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다.

각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다.

A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다.

각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다.

점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.

A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.

다음은 n = 4인 예시입니다.

주사위구성
#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를 가져간 뒤 6, 3을 굴리고, B가 주사위 #3, #4를 가져간 뒤 4, 1을 굴린다면 A의 승리입니다. (6 + 3 > 4 + 1)

A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.

A의 주사위승무패
#1, #2596196504
#1, #3560176560
#1, #4616184496
#2, #3496184616
#2, #4560176560
#3, #4504196596

A가 승리할 확률이 가장 높아지기 위해선 주사위 #1, #4를 가져가야 합니다.

주사위에 쓰인 수의 구성을 담은 2차원 정수 배열 dice가 매개변수로 주어집니다.

이때, 자신이 승리할 확률이 가장 높아지기 위해 A가 골라야 하는 주사위 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

승리할 확률이 가장 높은 주사위 조합이 유일한 경우만 주어집니다.

제한사항

  • 2 ≤ dice의 길이 = n ≤ 10
    • n은 2의 배수입니다.
    • dice[i]는 i+1번 주사위에 쓰인 6개의 수를 담고 있습니다.
    • dice[i]의 길이 = 6
    • 1 ≤ dice[i]의 원소 ≤ 100

입출력 예

diceresult
[[1, 2, 3, 4, 5, 6], [3, 3, 3, 3, 4, 4], [1, 3, 3, 4, 4, 4], [1, 1, 4, 4, 5, 5]][1, 4]
[[1, 2, 3, 4, 5, 6], [2, 2, 4, 4, 6, 6]][2]
[[40, 41, 42, 43, 44, 45], [43, 43, 42, 42, 41, 41], [1, 1, 80, 80, 80, 80], [70, 70, 1, 1, 70, 70]][1, 3]

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

주사위구성
#1[1, 2, 3, 4, 5, 6]
#2[2, 2, 4, 4, 6, 6]

A가 주사위 #2를 가져갔을 때 승리할 확률이 가장 높습니다. A가 #2, B가 #1 주사위를 굴린 결과에 따른 승패는 아래 표와 같습니다.

주사위 결과1 (B)2 (B)3 (B)4 (B)5 (B)6 (B)
2 (A)승무패패패패
2 (A)승무패패패패
4 (A)승승승무패패
4 (A)승승승무패패
6 (A)승승승승승무
6 (A)승승승승승무

입출력 예 #3

주사위구성
#1[40, 41, 42, 43, 44, 45]
#2[43, 43, 42, 42, 41, 41]
#3[1, 1, 80, 80, 80, 80]
#4[70, 70, 1, 1, 70, 70]

A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.

A의 주사위승무패
#1, #270416576
#1, #393624336
#1, #436024912
#2, #391224360
#2, #433624936
#3, #457616704

따라서 A가 주사위 #1, #3을 가져갔을 때 승리할 확률이 가장 높습니다.

풀이

golang code 주석 참조

golang

코드 ```golang // Find the best combination of dice for Player A func solution(dice [][]int) []int { n := len(dice) combinations := [][]int{} generateCombinations(n, []int{}, 0, &combinations) maxWins := -1 // Initialize with -1 to handle cases where no wins are possible var bestCombo []int for _, combo := range combinations { diceA, diceB := make([][]int, 0, len(combo)), make([][]int, 0, n-len(combo)) for i := 0; i < n; i++ { if contains(combo, i) { diceA = append(diceA, dice[i]) } else { diceB = append(diceB, dice[i]) } } sumA := rollDiceSums(diceA) sumB := rollDiceSums(diceB) wins := countWins(sumA, sumB) if wins > maxWins || (wins == maxWins && compareCombos(combo, bestCombo)) { maxWins = wins bestCombo = make([]int, len(combo)) copy(bestCombo, combo) } } // Convert 0-based indices to 1-based for i := range bestCombo { bestCombo[i]++ } return bestCombo } // Generate all combinations of choosing n/2 dice from n dice func generateCombinations(n int, combination []int, start int, results *[][]int) { if len(combination) == n/2 { comboCopy := make([]int, n/2) copy(comboCopy, combination) *results = append(*results, comboCopy) return } for i := start; i < n; i++ { combination = append(combination, i) generateCombinations(n, combination, i+1, results) combination = combination[:len(combination)-1] } } // Calculate the sum of all possible outcomes for a set of dice func rollDiceSums(dice [][]int) []int { sums := []int{0} for _, die := range dice { newSums := []int{} for _, roll := range die { for _, sum := range sums { newSums = append(newSums, sum+roll) } } sums = newSums } return sums } // Count the number of wins for A func countWins(arrA []int, arrB []int) int { sort.Ints(arrA) // slices.Sort(arrA) sort.Ints(arrB) // slices.Sort(arrB) wins := 0 i, j := 0, 0 for i < len(arrA) && j < len(arrB) { if arrA[i] > arrB[j] { wins += len(arrA) - i j++ } else { i++ } } return wins } // Compare two combinations, returns true if combo1 should be prioritized over combo2 func compareCombos(combo1, combo2 []int) bool { for i := 0; i < len(combo1) && i < len(combo2); i++ { if combo1[i] != combo2[i] { return combo1[i] < combo2[i] } } return len(combo1) < len(combo2) // In case one combo is a prefix of the other } func contains(slice []int, val int) bool { for _, item := range slice { if item == val { return true } } return false } ```
결과 정확성 | 테스트 ---|--- 테스트 1|통과 (0.04ms, 4.11MB) 테스트 2|통과 (0.01ms, 4.2MB) 테스트 3|통과 (0.01ms, 3.54MB) 테스트 4|통과 (0.01ms, 3.55MB) 테스트 5|통과 (0.01ms, 3.55MB) 테스트 6|통과 (0.01ms, 4.2MB) 테스트 7|통과 (0.06ms, 3.54MB) 테스트 8|통과 (0.06ms, 3.56MB) 테스트 9|통과 (0.06ms, 4.23MB) 테스트 10|통과 (0.06ms, 4.41MB) 테스트 11|통과 (0.06ms, 4.21MB) 테스트 12|통과 (0.04ms, 4.2MB) 테스트 13|통과 (0.67ms, 4.2MB) 테스트 14|통과 (0.57ms, 4.23MB) 테스트 15|통과 (0.64ms, 4.3MB) 테스트 16|통과 (1.18ms, 4.12MB) 테스트 17|통과 (1.19ms, 3.57MB) 테스트 18|통과 (0.89ms, 4.21MB) 테스트 19|통과 (262.59ms, 13.7MB) 테스트 20|통과 (227.19ms, 10.4MB) 테스트 21|통과 (242.37ms, 8.67MB) 테스트 22|통과 (534.86ms, 10.7MB) 테스트 23|통과 (522.70ms, 12.2MB) 테스트 24|통과 (410.62ms, 8.29MB) 테스트 25|통과 (365.46ms, 8.85MB) 테스트 26|통과 (339.13ms, 8.73MB)

java

코드 ```java class Solution { public int[] solution(int[][] dice) { int n = dice.length; List<List> combinations = generateCombinations(n, new ArrayList<>(), 0, new ArrayList<>()); int maxWins = -1; List bestCombo = new ArrayList<>(); for (List combo : combinations) { List sumA = rollDiceSums(selectDice(dice, combo)); List sumB = rollDiceSums(selectDice(dice, complement(combo, n))); int wins = countWins(sumA, sumB); if (wins > maxWins || (wins == maxWins && compareCombos(combo, bestCombo))) { maxWins = wins; bestCombo = new ArrayList<>(combo); } } // Convert to 1-based and to array return bestCombo.stream().mapToInt(i -> i + 1).toArray(); } private static List<List> generateCombinations(int n, List current, int start, ArrayList<List> result) { if (current.size() == n / 2) { result.add(new ArrayList<>(current)); return result; } for (int i = start; i < n; i++) { current.add(i); generateCombinations(n, current, i + 1, result); current.remove(current.size() - 1); } return result; } private static List rollDiceSums(List<int[]> dice) { List sums = new ArrayList<>(); sums.add(0); for (int[] die : dice) { List newSums = new ArrayList<>(); for (int side : die) { for (int existingSum : sums) { newSums.add(existingSum + side); } } sums = newSums; } return sums; } private static int countWins(List arrA, List arrB) { Collections.sort(arrA); Collections.sort(arrB); int wins = 0, i = 0, j = 0; while (i < arrA.size() && j < arrB.size()) { if (arrA.get(i) > arrB.get(j)) { wins += arrA.size() - i; j++; } else { i++; } } return wins; } private static boolean compareCombos(List combo1, List combo2) { for (int i = 0; i < Math.min(combo1.size(), combo2.size()); i++) { if (!Objects.equals(combo1.get(i), combo2.get(i))) { return combo1.get(i) < combo2.get(i); } } return combo1.size() < combo2.size(); } private static List<int[]> selectDice(int[][] dice, List indices) { List<int[]> selected = new ArrayList<>(); for (int index : indices) { selected.add(dice[index]); } return selected; } private static List complement(List combo, int n) { List comp = new ArrayList<>(); for (int i = 0; i < n; i++) { if (!combo.contains(i)) { comp.add(i); } } return comp; } } ``` </details>
결과 정확성 | 테스트 ---|--- 테스트 1|통과 (29.33ms, 95.3MB) 테스트 2|통과 (10.01ms, 66.5MB) 테스트 3|통과 (11.52ms, 76.1MB) 테스트 4|통과 (11.33ms, 77.7MB) 테스트 5|통과 (10.93ms, 77.8MB) 테스트 6|통과 (12.29ms, 72.5MB) 테스트 7|통과 (12.50ms, 79.3MB) 테스트 8|통과 (11.00ms, 90.6MB) 테스트 9|통과 (16.17ms, 78.7MB) 테스트 10|통과 (21.58ms, 81.1MB) 테스트 11|통과 (24.47ms, 76.5MB) 테스트 12|통과 (13.42ms, 83.7MB) 테스트 13|통과 (23.73ms, 81.2MB) 테스트 14|통과 (31.50ms, 76.1MB) 테스트 15|통과 (21.58ms, 77.2MB) 테스트 16|통과 (42.00ms, 73.7MB) 테스트 17|통과 (63.25ms, 84.8MB) 테스트 18|통과 (22.45ms, 72.6MB) 테스트 19|통과 (628.90ms, 126MB) 테스트 20|통과 (848.44ms, 136MB) 테스트 21|통과 (727.23ms, 127MB) 테스트 22|통과 (965.70ms, 161MB) 테스트 23|통과 (795.44ms, 166MB) 테스트 24|통과 (794.07ms, 156MB) 테스트 25|통과 (633.76ms, 161MB) 테스트 26|통과 (682.79ms, 175MB)
#### kotlin
코드 ```kotlin class Solution { fun solution(dice: Array): IntArray { val n = dice.size val combinations = generateCombinations(n) var maxWins = -1 var bestCombo: List = listOf() combinations.forEach { combo -> val sumA = rollDiceSums(selectDice(dice, combo)) val sumB = rollDiceSums(selectDice(dice, complement(combo, n))) val wins = countWins(sumA, sumB) if (wins > maxWins || (wins == maxWins && compareCombos(combo, bestCombo))) { maxWins = wins bestCombo = combo.toList() } } // Convert to 1-based and to array return bestCombo.map { it + 1 }.toIntArray() } private fun generateCombinations(n: Int, current: MutableList = mutableListOf(), start: Int = 0): List<List> { val result = mutableListOf<List>() if (current.size == n / 2) { result.add(ArrayList(current)) return result } for (i in start until n) { current.add(i) result.addAll(generateCombinations(n, current, i + 1)) current.removeAt(current.size - 1) } return result } private fun rollDiceSums(dice: List): List { var sums = mutableListOf(0) dice.forEach { die -> val newSums = mutableListOf() die.forEach { side -> sums.forEach { sum -> newSums.add(sum + side) } } sums = newSums } return sums } private fun countWins(arrA: List, arrB: List): Int { val sortedA = arrA.sorted() val sortedB = arrB.sorted() var wins = 0 var i = 0 var j = 0 while (i < sortedA.size && j < sortedB.size) { if (sortedA[i] > sortedB[j]) { wins += sortedA.size - i j++ } else { i++ } } return wins } private fun compareCombos(combo1: List, combo2: List): Boolean { for (i in 0 until minOf(combo1.size, combo2.size)) { if (combo1[i] != combo2[i]) { return combo1[i] < combo2[i] } } return combo1.size < combo2.size } private fun selectDice(dice: Array, indices: List): List { return indices.map { dice[it] } } private fun complement(combo: List, n: Int): List { return (0 until n).filterNot { it in combo } } } ``` </details>
결과 정확성 | 테스트 ---|--- 테스트 1|통과 (20.97ms, 64.4MB) 테스트 2|통과 (26.38ms, 63.6MB) 테스트 3|통과 (19.53ms, 64.4MB) 테스트 4|통과 (26.51ms, 63.5MB) 테스트 5|통과 (26.93ms, 63.4MB) 테스트 6|통과 (31.97ms, 64.3MB) 테스트 7|통과 (24.56ms, 65.3MB) 테스트 8|통과 (31.50ms, 64.3MB) 테스트 9|통과 (20.44ms, 64.8MB) 테스트 10|통과 (22.84ms, 65MB) 테스트 11|통과 (36.47ms, 63.8MB) 테스트 12|통과 (30.59ms, 62.6MB) 테스트 13|통과 (30.76ms, 63.5MB) 테스트 14|통과 (35.38ms, 64.2MB) 테스트 15|통과 (34.14ms, 63.4MB) 테스트 16|통과 (30.14ms, 64.8MB) 테스트 17|통과 (33.67ms, 64.7MB) 테스트 18|통과 (40.22ms, 64.4MB) 테스트 19|통과 (965.92ms, 109MB) 테스트 20|통과 (711.08ms, 109MB) 테스트 21|통과 (772.02ms, 109MB) 테스트 22|통과 (1081.66ms, 180MB) 테스트 23|통과 (1068.28ms, 178MB) 테스트 24|통과 (1036.81ms, 169MB) 테스트 25|통과 (1049.92ms, 179MB) 테스트 26|통과 (920.19ms, 179MB)
#### python
코드 ```python from itertools import combinations def generate_combinations(n): return list(combinations(range(n), n // 2)) def roll_dice_sums(selected_dice): sums = [0] for die in selected_dice: new_sums = [] for side in die: for existing_sum in sums: new_sums.append(existing_sum + side) sums = new_sums return sums def count_wins(arr_a, arr_b): arr_a.sort() arr_b.sort() wins = i = j = 0 while i < len(arr_a) and j < len(arr_b): if arr_a[i] > arr_b[j]: wins += len(arr_a) - i j += 1 else: i += 1 return wins def compare_combos(combo1, combo2): for i in range(min(len(combo1), len(combo2))): if combo1[i] != combo2[i]: return combo1[i] < combo2[i] return len(combo1) < len(combo2) def solution(dice): n = len(dice) combinations = generate_combinations(n) max_wins = -1 best_combo = [] for combo in combinations: sum_a = roll_dice_sums([dice[i] for i in combo]) sum_b = roll_dice_sums([dice[i] for i in range(n) if i not in combo]) wins = count_wins(sum_a, sum_b) if wins > max_wins or (wins == max_wins and compare_combos(combo, best_combo)): max_wins = wins best_combo = combo # Convert to 1-based and return return [i + 1 for i in best_combo] ```
결과 정확성 | 테스트 ---|--- 테스트 1|통과 (0.14ms, 10.2MB) 테스트 2|통과 (0.02ms, 10.3MB) 테스트 3|통과 (0.03ms, 10.3MB) 테스트 4|통과 (0.03ms, 10.1MB) 테스트 5|통과 (0.04ms, 10.4MB) 테스트 6|통과 (0.02ms, 10.4MB) 테스트 7|통과 (0.17ms, 10.3MB) 테스트 8|통과 (0.17ms, 10.1MB) 테스트 9|통과 (0.18ms, 10.3MB) 테스트 10|통과 (0.31ms, 10.3MB) 테스트 11|통과 (0.28ms, 10.2MB) 테스트 12|통과 (0.18ms, 10.1MB) 테스트 13|통과 (3.18ms, 10.1MB) 테스트 14|통과 (4.04ms, 10.4MB) 테스트 15|통과 (3.14ms, 10.4MB) 테스트 16|통과 (6.22ms, 10.1MB) 테스트 17|통과 (5.42ms, 10.2MB) 테스트 18|통과 (3.62ms, 10.4MB) 테스트 19|통과 (1838.89ms, 10.2MB) 테스트 20|통과 (1856.05ms, 10.4MB) 테스트 21|통과 (1800.51ms, 10.3MB) 테스트 22|통과 (1678.56ms, 10.6MB) 테스트 23|통과 (1830.17ms, 10.8MB) 테스트 24|통과 (1641.36ms, 10.4MB) 테스트 25|통과 (1740.16ms, 10.4MB) 테스트 26|통과 (1707.88ms, 10.5MB)
#### javascript
코드 ```javascript function generateCombinations(n) { const result = []; const combinations = (prefix = [], start = 0) => { if (prefix.length === n / 2) { result.push([...prefix]); return; } for (let i = start; i < n; i++) { combinations([...prefix, i], i + 1); } }; combinations(); return result; } function rollDiceSums(selectedDice) { let sums = [0]; for (const die of selectedDice) { const newSums = []; for (const side of die) { for (const existingSum of sums) { newSums.push(existingSum + side); } } sums = newSums; } return sums; } function countWins(arrA, arrB) { arrA.sort((a, b) => a - b); arrB.sort((a, b) => a - b); let wins = 0, i = 0, j = 0; while (i < arrA.length && j < arrB.length) { if (arrA[i] > arrB[j]) { wins += arrA.length - i; j++; } else { i++; } } return wins; } function compareCombos(combo1, combo2) { for (let i = 0; i < Math.min(combo1.length, combo2.length); i++) { if (combo1[i] !== combo2[i]) { return combo1[i] < combo2[i]; } } return combo1.length < combo2.length; } function solution(dice) { const n = dice.length; const combinations = generateCombinations(n); let maxWins = -1; let bestCombo = []; for (const combo of combinations) { const sumA = rollDiceSums(combo.map(i => dice[i])); const sumB = rollDiceSums([...Array(n).keys()].filter(i => !combo.includes(i)).map(i => dice[i])); const wins = countWins(sumA, sumB); if (wins > maxWins || (wins === maxWins && compareCombos(combo, bestCombo))) { maxWins = wins; bestCombo = combo; } } // Convert to 1-based and return return bestCombo.map(i => i + 1); } ```
결과 정확성 | 테스트 ---|--- 테스트 1|통과 (0.62ms, 33.5MB) 테스트 2|통과 (0.38ms, 33.4MB) 테스트 3|통과 (0.49ms, 33.6MB) 테스트 4|통과 (0.40ms, 33.5MB) 테스트 5|통과 (0.60ms, 33.4MB) 테스트 6|통과 (0.40ms, 33.5MB) 테스트 7|통과 (0.60ms, 33.5MB) 테스트 8|통과 (0.79ms, 33.4MB) 테스트 9|통과 (0.97ms, 33.5MB) 테스트 10|통과 (0.59ms, 33.5MB) 테스트 11|통과 (0.61ms, 33.5MB) 테스트 12|통과 (0.94ms, 33.4MB) 테스트 13|통과 (4.56ms, 37.1MB) 테스트 14|통과 (4.59ms, 37.1MB) 테스트 15|통과 (4.45ms, 37.1MB) 테스트 16|통과 (7.40ms, 37MB) 테스트 17|통과 (4.86ms, 37.1MB) 테스트 18|통과 (6.25ms, 37MB) 테스트 19|통과 (828.75ms, 52.5MB) 테스트 20|통과 (856.11ms, 51.7MB) 테스트 21|통과 (901.49ms, 51.3MB) 테스트 22|통과 (1049.64ms, 51.4MB) 테스트 23|통과 (1024.95ms, 51.5MB) 테스트 24|통과 (1057.35ms, 51.5MB) 테스트 25|통과 (928.35ms, 51.4MB) 테스트 26|통과 (953.48ms, 51.6MB)
coding test, 2024 kakao winter internship
coding test 2024 kakao winter internship
This post is licensed under CC BY 4.0 by the author.