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

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

프로그래머스

 

문제 접근

 

1. 완전탐색

만약 6개의 주사위에 대해 완전탐색을 한다면, 6개를 3개씩 나눠갖는 조합, 그리고 A, B가 각자 3개의 주사위를 굴리고, 각각의 모든 경우에 대해 합까지 비교하는.. 시간초과가 발생하지 않을까라는 생각을 했다. 

 

2. 이분탐색

주사위를 절반으로 나눠서 A, B가 각자 주사위를 굴리는 것까지는 같지만, 주사위의 합을 비교하는 과정에서 이분탐색으로 시간을 줄일 수 있지 않을까라는 생각을 했다.(풀이 참고)

     (1) A, B가 각자 고른 주사위로 만들 수 있는 주사위의 합을 각자 리스트에 저장

     (2) B 리스트 정렬 후, A의 각 원소들로 leftmost 이분탐색 실시 

           => 반환되는 인덱스 값이 A의 원소로 B 리스트에서 이길 수 있는 경우의 수 

           => 그리고 위의 SUM이 현재 주사위 조합으로 이길 수 있는 모든 경우의 수 

 

dic = { }

(key: 이길 수 있는 경우의 수, value는 그때의 주사위 번호들)

 

코드

from itertools import combinations, product # 조합, 중복순열 라이브러리
from bisect import bisect_left  # 이진 탐색 라이브러리

def solution(dice):
    dic = {}
    
    L = len(dice)
    
    # A와 B의 주사위 번호의 조합 생성
    for A in combinations(range(L), L//2):
        B = [i for i in range(L) if i not in A]
        
        A_sum, B_sum = [], []
        
        # 주사위의 모든 가능한 합을 구해 저장
        for order_product in product(range(6), repeat = L//2):
            A_sum.append(sum(dice[i][j] for i, j in zip(A, order_product)))
            B_sum.append(sum(dice[i][j] for i, j in zip(B, order_product)))
        B_sum.sort()
        
        wins = sum(bisect_left(B_sum, num) for num in A_sum)
        
        # 승리 횟수는 키, 승리한 조합은 값
        dic[wins] = list(A)
    
    max_key = max(dic.keys())
    
    return [x+1 for x in dic[max_key]]