[Lv_3] 주사위 고르기

1. 2024 KAKAO WINTER INTERNSHIP

combi = []
perm = []
def solution(dice):
    leng = len(dice)
    generate(leng, [], 0, 0)
    permu(leng / 2, [], 0)
    
    max_winrate = 0
    max_dice = []
    
    count = 0
    
    for arr in combi:        
        b_arr = []
        
        for i in range(leng):
            if i not in arr:
                b_arr.append(i)
                
        red = {}
        blue = {}
        
        for p in perm:
            a_val = 0
            for i in range(len(arr)):
                a_val += dice[arr[i]][p[i]]
            red[a_val] = red.get(a_val, 0) + 1
            
            b_val = 0
            for i in range(len(b_arr)):
                b_val += dice[b_arr[i]][p[i]]
            blue[b_val] = blue.get(b_val, 0) + 1
            
        #print(red, blue)
        
        s_red = sorted(red.items(), key = lambda item: item[0])
        s_blue = sorted(blue.items(), key = lambda item: item[0])

        red_win = 0
        
        for aVal in s_red:
            for bVal in s_blue:
                if aVal[0] > bVal[0]:
                    red_win += aVal[1] * bVal[1]
                
        win_rate = red_win / pow(6, leng)
        
        if win_rate > max_winrate:
            max_winrate = win_rate
            #print(arr)
            max_dice = arr
        
    return list(map(lambda x: x + 1, max_dice))

# A가 가져갈 주사위
def generate(leng, buck, count, start):
    if count == leng / 2:
        combi.append(buck.copy())
        return
        
    for i in range(start, leng):
        buck.append(i)
        generate(leng, buck, count+1, i+1)
        buck.pop()

# 주사위가 나올 경우의 수
def permu(max, buck, count):
    if max == count:
        perm.append(buck.copy())
        return
    for i in range(6):
        buck.append(i)
        permu(max, buck, count+1)
        buck.pop()

완전탐색으로 풀 경우 효율 '시간초과'가 발생한다.

예를 들어, 4개의 주사위를 굴린다면 모든 주사위를 고려할 경우 6^4의 경우의 수이지만

A가 2개의 주사위를 픽한 결과의 값과 B가 픽한 결과의 값을 사전에 저장해 비교하면 훨씬 줄어든 경우의 수로 대처 가능하다.

 

✔️ 링크: 코딩테스트 연습 - 주사위 고르기 | 프로그래머스 스쿨 (programmers.co.kr)