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

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

프로그래머스

 

완전탐색을 통해 구현력을 테스트하는 문제인 것 같다.

 

첫 번째로 각 주사위를 값: 등장 횟수의 딕셔너리로 바꾸었다.

주사위가 [3,3,3,3,4,4] 면 {3:4, 4:2}로 변환하였다.

 

두 번째로는 combinations를 통해 주사위를 선택할 수 있는 케이스들을 전부 구하고 각 케이스에 대해 첫 번째 단계에서 변환된 딕셔너리로 선택된 주사위들로 나올 수 있는 합: 경우의 수 딕셔너리를 구하였다.

주사위 1이 {3:4,4:2}고  주사위 2가 {2:2,5:4}인 경우 3+2는 4*2번 등장하고 3+5는 4*4번 등장한다.

{5:8, 6:4, 8:16, 9:8}이 나오게 된다. 

이렇게 계산된 딕셔너리와 다음 주사위를 반복해서 계산해서 선택된 주사위들의 합: 경우의 수 딕셔너리를 생성한다.

combinations에서 선택되지 않은 주사위들로 한 번 더 반복해 주사위 b의 전체 경우의 수를 구한다.

 

세 번째는 두번째함수에서 계산된 a의 총 경우의수 와 b의 총 경우의 수를 비교하여 최종 승리, 패배 경우의 수를 구한다.

 

마지막으로 세번째 함수에서 계산한 최종 승리, 패배 경우의 수의 최댓값을 저장하고, 최대 승리수가 최대 패배수보다 많다면 a의 주사위를 리턴하고, 만약 최대 패배수가 많다면 b의 최대승리수가 많다는 의미이므로 b의 주사위를 리턴한다.

 

 

from itertools import combinations

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

# 각 주사위를 값: 등장횟수 딕셔너리로 변환
def diceToProb(dice):
    result = {}
    for x in dice:
        if not x in result:
            result[x] = 0
        result[x] += 1          
    return result

# 각 주사위들의 값: 등장횟수 를 곱하여 합: 등장경우의 수 딕셔너리 생성
def calcSumProb(diceList):
    result = {0:1}
    i = 0
    while i < len(diceList):
        temp = {}
        for k1,v1 in result.items():
            for k2,v2 in diceList[i].items():
                if not k1+k2 in temp:
                    temp[k1+k2] = 0
                temp[k1+k2] += v1*v2
        i += 1
        result = temp            
    return result   

# 계산된 합: 등장경우의 수를 비교하여 최종 승,패 수 계산
def countWin(sumA,sumB):
    result =[0,0]
    for k1,v1 in sumA.items():
        for k2,v2 in sumB.items():
            if k1>k2:
                result[0] += v1*v2
            elif k2>k1:
                result[1] += v1*v2
    return result
        

# 위에 모든 단계를 통해 최종 승,패 수 계산
def prob(dice, selected):
    diceA = []
    diceB = []
    for i in range(len(dice)):
        if i in selected:
            diceA.append(diceToProb(dice[i]))
        else:
            diceB.append(diceToProb(dice[i]))

    sumA = calcSumProb(diceA)
    sumB = calcSumProb(diceB)
    
    return countWin(sumA,sumB)
    
    
def solution(dice):
    answer = []
    
    # 주사위를 나눌수 있는 모든 경우의수의 절반 탐색
    l = len(dice)
    combcase = list(combinations(range(l),l//2))
    
    maxWin, maxLose = -1,-1
    maxWinCase, maxLoseCase = [],[]
    
    for i in range(len(combcase)//2):
        win, lose = prob(dice,combcase[i])
        if win>maxWin:
            maxWin = win
            maxWinCase = list(combcase[i])
        if lose>maxLose:
            maxLose = lose
            maxLoseCase = list(combcase[i])
    
    # A가 이긴횟수가 많다면 combcase 그대로 사용
    if maxWin>maxLose:
        answer = maxWinCase
    
    # 아니라면 B의 주사위를 사용
    else:
        answer = [x for x in range(l) if not x in maxLoseCase]
    
    answer = [x+1 for x in answer]
    answer.sort()
    
    return answer