개발/알고리즘

[카카오 프로그래머스] 주사위 고르기

개발자_티모 2024. 4. 7. 02:10
반응형

문제 이해하기

N개의 주사위가 주어지고, 해당 주사위에는 6개의 면에 랜덤한 숫자들이 적혀있음

이 N개의 주사위 중 N/2를 A가 가져가고, 나머지를 B가 가져가고 이렇게 가져간 주사위 중 승률이 가장 높은 주사위를 반환해야함

문제 해결 방법

1. 주사위 선택을 어떻게 하냐에 따라서 결과 값이 달라지기 완전탐색을 진행해야 합니다. 파이썬에서는 combinations 함수를 통해서 주사위 조합을 구할 수 있습니다.

    combi = list(combinations(range(0, len(dice)), n))

 

2. 내가 선택한 주사위에서 나올 수 있는 면들의 조합, 상대 방이 선택한 주사위에서 나올 수 있는 면들의 조합을 구해야 합니다.

for my_dice in combi:
    enemy_dice = list(set(range(len(dice))) - set(my_dice))

    my_score = []
    enemy_score = []

    for dice_cand in product(range(6), repeat=n):
        my_score.append(sum(dice[i][j] for i, j in zip(my_dice, dice_cand)))
        enemy_score.append(sum(dice[i][j] for i, j in zip(enemy_dice, dice_cand)))

 

 

3. 그 후 내가 나온 점수와 상대방이 나온 점수를 모두 비교해서 몇 번 이겼는지 계산하면 됩니다.

for my_dice in combi:
    enemy_dice = list(set(range(len(dice))) - set(my_dice))

    my_score = []
    enemy_score = []

    for dice_cand in product(range(6), repeat=n):
        my_score.append(sum(dice[i][j] for i, j in zip(my_dice, dice_cand)))
        enemy_score.append(sum(dice[i][j] for i, j in zip(enemy_dice, dice_cand)))

 

여기서 중요한 점은 이기는 횟수를 계산하기 위해서는 최대 15,243,697,152(10C5 * 6**10)이 필요하게 됩니다.

 ** 내가 가져갈 수 있는 주사위의 최대 수가 5가 되고, 해당 5개의 조합 6**5과 6**5을 계산하는 경우의 수는 15,243,697,152(10C5 * 6**10)이 됩니다.

 

따라서 승리를 빠르게 판별하기 위해서 다른 방법이 필요하게 되는데 먼저 상대방의 점수 조합을 정렬한 후 내가 만든 숫자에서 이분탐색을 수행하는 것입니다.

 

이렇게 계산하면 연산횟수가 1,157,606로 줄어들게 됩니다.

 ** 6*5을 정렬하면 연산횟수는  61,362가 되고 여기에 252(10C5)를 곱해주면 됩니다.

 

따라서 아래와 같이 이분탐색을 진행하고 찾아진 인덱스가 이길 수 있는 최대 개수가 됩니다.

 

코드

from bisect import bisect_left
from itertools import combinations, product

def solution(dice):
    ans = []
    ans_score = -1
    
    n = int(len(dice) / 2)
     
    combi = list(combinations(range(0, len(dice)), n))
    
    for my_dice in combi:
        enemy_dice = list(set(range(len(dice))) - set(my_dice))
        
        my_score = []
        enemy_score = []
        
        for dice_cand in product(range(6), repeat=n):
            my_score.append(sum(dice[i][j] for i, j in zip(my_dice, dice_cand)))
            enemy_score.append(sum(dice[i][j] for i, j in zip(enemy_dice, dice_cand)))
        
        enemy_score.sort()
        can_win = sum(bisect_left(enemy_score, my) for my in my_score)
        
        if ans_score < can_win:
            ans = [dice + 1 for dice in my_dice]
            ans_score = can_win
            
    return ans
        
    
if __name__ == "__main__":
    dice = [[1, 2, 3, 4, 5, 6], [3, 3, 3, 3, 4, 4], [1, 3, 3, 4, 4, 4], [1, 1, 4, 4, 5, 5]]
    
    print(solution(dice))

 

배운점 정리하기

주어진 배열에서 특정 값을 찾는 것은 이분탐색을 활용하면 빠르게 해결할 수 있다는 점을 다시 한번 상기할 수 있었다.

 

반응형