[99클럽/파이썬 챌린저/26일차] 주사위 고르기

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

문제 설명
A와 B가 n개의 주사위를 가지고 승부를 합니다. 주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다. 각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다. A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다. 각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다. 점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다. A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다. 주사위에 쓰인 수의 구성을 담은 2차원 정수 배열 dice가 매개변수로 주어집니다. 이때, 자신이 승리할 확률이 가장 높아지기 위해 A가 골라야 하는 주사위 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 승리할 확률이 가장 높은 주사위 조합이 유일한 경우만 주어집니다.

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

입출력 예

dice	result
[[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]

 

 

위 글을 참고하여 풀이 했다.

 

코테 문제를 많이 풀어오며 대부분 기능들을 다 써봤다고 생각했는데, 아니었다.

중복 순열을 만드는 product나, iterable 객체를 튜플 형태로 묶는 zip은 한 번도 사용한 적 없어서 이번 풀이는 참 신기했다.

이진 탐색도 함수로서 제공하는 게 참.. 신기한 문제였다.

 

모든 주사위의 경우의 수를 확인해야 한다.  combination 사용

각 주사위의 묶음이 만들 수 있는 수들을 담고 정렬한다.  

A주사위의 묶음의 요소가 B주사위의 묶음을 몇 번 이겨야 하는지 이진 탐색을 이용해서 구한다.

 

가장 승리 횟수가 높은 묶음을 출력한다.

 

from itertools import combinations
from itertools import product
from bisect import bisect_left

def solution(dice):
      
        
    result = {}
    max_result = 0
    dice_num = len(dice)
    for a_comb in combinations(range(dice_num), dice_num//2):
        b_comb = [i for i in range(dice_num) if i not in a_comb]
        
        can_a, can_b = [], []
        for can in product(range(6), repeat=dice_num//2):
            can_a.append(sum(dice[i][j] for i, j in zip(a_comb, can)))
            can_b.append(sum(dice[i][j] for i, j in zip(b_comb, can)))
        can_b.sort()
        
        res = sum(bisect_left(can_b, i) for i in can_a)
        result[res] = list(a_comb)
        max_result = max(max_result, res)
        
    ans = [i+1 for i in result[max_result]]
    
    return ans​

 

 

---