(프로그래머스 Lv.3) 주사위 고르기 / with.조합,이진탐색

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/258709

코드

from itertools import combinations, product
from bisect import bisect_left

def solution(dice):
    n = len(dice)
    a = n // 2
    best_win_count = -1
    best_combo = []

    for a_combo in combinations(range(n), a):
        b_combo = [i for i in range(n) if i not in a_combo]
        
        a_sums = []
        b_sums = []

        a_dice = [dice[i] for i in a_combo]  
        for a_rolls in product(*a_dice):    
            a_sum = sum(a_rolls)             
            a_sums.append(a_sum)             
        
        b_dice = [dice[i] for i in b_combo]
        for b_rolls in product(*b_dice):     
            b_sum = sum(b_rolls)             
            b_sums.append(b_sum)             
        
        a_sums.sort()
        b_sums.sort()
        
        win_count = 0
        for a_sum in a_sums:
            win_count += bisect_left(b_sums, a_sum)
        
        if win_count > best_win_count:
            best_win_count = win_count
            best_combo = [i + 1 for i in a_combo]

    return sorted(best_combo)

풀이

1. A가 n개의 주사위에서 a개 만큼 뽑아서 나올 수 있는 조합을 구한다. for a_combo in combinations(range(n), a): 예를 들어 주사위가 4개 있을 때 a는 n//2만큼 주사위를 뽑을 수 있다고 했다. 그렇다면 A가 뽑을 수 있는 주사위의 개수는 2개이다. 고로 dice의 인덱스 번호가 1부터라고 가정할 때 여기서 a개만큼의 조합을 구하면, [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]
   1. a의 조합을 제외한 나머지를 b의 조합으로 설정한다. 예를 들어 a가 현재 (1,2)의 조합이라면 b는 (3,4)가 될 것이다.
   2. a의 조합에서 나올 수 있는 주사위 눈의 경우의 수를 구하고, 그 주사위 눈이 나올 때마다 각각의 총합은 어떻게 되는지를 구한다. b도 마찬가지로 똑같이 구한다.
      1. 이 때 경우의 수는 중복 조합(==product)로 구한다. 왜? 같은 숫자의 주사위 눈이 나올 수도 있기때문이다. 이는 permutations를 사용하면 안되는 이유와도 귀결된다.
      2. 참고로 중복 조합을 구할 때 언패킹을 하는 이유는, 현재 a_dice의 형태가 [[1,2,3], [3,3,3]] 이런 식으로 이중리스트로 담겨있다. 근데 여기서 언패킹을 안 하고 product 메서드를 바로 씌우면, 이중리스트 자체를 하나의 값으로 보기에 조합이 이상하게 구해질 것이다. 따라서 각 원소별로 그 합을 구하기 위해 언패킹을 한다.
   3. 앞에서 a와 b의 총합을 구했다면, a가 이기는 경우의 수를 계산해주면 된다. 이는 이진탐색으로 구한다.
      1. 왜? 하나하나 다 비교하면 시간초과가 난다. 왜? dice의 원소가 최대 100까지 들어갈 수 있는데, 이러면 경우의 수가 최악의 경우에는 진짜 겁나 많을테니까, 이진탐색으로 구해야 된다.
      2. 그렇다면 이진탐색의 원리를 생각해보자. 이진탐색의 기본 조건은 리스트가 정렬되어 있어야 한다. 정렬 후 bisect_left 메서드를 활용해서 a_sums의 원소를 하나씩 빼낸 다음, a_sums의 원소 값이 b_sums에 있는 값 보다 작거나 같다면 그 원소의 인덱스 값을 win_count에 저장하면 된다.
         1. 왜? 만약 b_sums에 저장되어 있는 주사위 눈의 합은 [10, 20, 30]이고, a_sum은 20이라고 가정해보자. 그럼 이 때 bisect_left를 하면 반환 값은 1이 나올 것 이며, 이는 a가 승리할 수 있는 횟수와 같다.
   4. best_win_count 보다 현재의 승리 횟수가 많다면 이를 best_win_count 값으로 갱신 하고, return할 값인 best_combo의 원소에 각각 +1을 한다. 왜? 인덱스 넘버는 0번부터인데, 정답은 그 값에 +1한 값을 return해야되기 때문이다.
2. 마지막으로 주사위 인덱스 번호를 오름차순으로 정렬해서 리턴하라 했으니까, sorted() 메서드를 사용해서 값을 반환하면 끝.

Permutations VS Combinations VS Product

• Permutaions: 앞 뒤 순서를 고려하고 구하는 조합
• Combinations: 앞 뒤 순서를 고려하지 않고 구하는 조합
• Product: 그 전에 선택한 값 포함해서 구하는 조합

오답 풀이

Q. dice의 max값이 6이라고 할 때 A가 이기려면 A는 6이 가장 많이 포함 되어있는 주사위를 뽑으면 되지 않나? 그래서 일단 주사위 번호를 한 개 구해놓고, 그 다음에 b 조합과 나머지 A가 뽑을 번호들의 승률을 계산하면 되지 않을까? => 네 안돼요~. 가장 큰 값이 있다고 해서 무조건 그 값이 포함되어있는 주사위의 승률이 높을거라는 보장이 없다.

내가 머큐리처럼 똑똑했으면 좋겠다…. 그럼 코테를 쉽게 풀었겠지……? ㅎㅎ…ㅠㅠ..ㅠ..ㅠ