[프로그래머스] 주사위 고르기(python)

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

프로그래머스

 

주사위 고르기 문제

A와 B가 주사위를 골랐을 때 A가 승리할 확률이 가장 높아지는 주사위 배열을 찾는 문제

 

#사용 알고리즘

조합(combination)

반복순열(product)

이진탐색(binary Search)

📌문제 접근 포인트

1. n의 범위가 10개이므로, A가 n개 중 n//2개를 뽑을 수 있는 경우의 수를 구하자.(조합, 최대 nCn//2), 이때, 최종적으로 반환해야 하는 주사위 조합이 인덱스의 형태로 반환해야 하니 인덱스로 조합 순서를 먼저 구해준 후, 선택한 주사위 값으로 반환해 주자.

2. 뽑은 주사위들의 합의 경우의 수(반복순열)를 전부 찾아주자. 각각의 구한 값에 대해 전체 승리 횟수를 구해줘야 하므로 전부 찾을 필요가 있다.

3. 여기서 A의 경우의 수를 찾았으니, 자연스럽게 B는 나머지 주사위를 자연스럽게 가져가게 된다. 이때 B의 경우 A와 대칭의 구조를 갖게 되므로 (위 예시의 승 <> 패가 대칭 구조인 것을 보면 알 수 있다) 인덱스를 대칭으로 맞춰주면 된다.

4. 이제 값의 비교를 위해 완전 탐색을 할 수 도 있겠지만 성능을 고려하여 이분 탐색을 적용한다. 여기서 A를 사전에 정렬해 두고, A의 값을 돌면서 B보다 작은 횟수들을 모두 더해나 나가도록 이분탐색을 적용해 주면 A가 승리하는 횟수를 알 수 있다.

5. 최대 비교를 통해 A의 승리 횟수를 저장하고, 그때의 인덱스를 찾아내어 값으로 반환해 주면 해결할 수 있다.

반응형

⚙ 내가 푼 정답 코드

from itertools import combinations, product

def solution(dice):
    n = len(dice)
    A, result = [], []
    cases = list(combinations(range(n), n//2)) # 뽑을 수 있는 경우의 수 (인덱스)
    
    for case in cases:
        dices = [dice[c] for c in case] # 인덱스에 해당하는 실제 주사위
        nums = sorted([sum(i) for i in product(*dices)]) # 뽑은 주사위의 합의 경우의 수
        A.append(nums)
        
    a, p = 0, len(A)
    for i in range(p):
        B = A[p-i-1] # B와 A는대칭의 구조를 가지므로 B = A[p-i-1]
        
        #각 조합이 이기는 횟수 이분탐색
        temp = 0
        for t in A[i]:
            left, right = 0, len(B)-1
            while left <= right:
                mid = (left + right) // 2
                if B[mid] < t:
                    left = mid + 1
                else :
                    right = mid - 1
            temp += left
        
        # 가장 승리 확률이 높은 경우의 수 반환
        if a < temp:
            a = temp
            result = [x + 1 for x in cases[i]]
    
    return result