주사위 고르기(카카오) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

여러 개의 주사위를 조합하여 그 중 승리할 확률이 가장 높은 주사위 조합을 찾는 문제이다.

모든 주사위 조합의 승리 수를 비교하며 그 중 최댓값을 구해야하기 때문에 완전 탐색을 통해 문제를 풀었다. 

 

문제를 풀 때 아래 사항에 대해 고민했고, 2번에서 많이 고전했다.

1. 주사위의 조합을 어떻게 표현할 것인가?
2. 주사위를 조합하여 비교를 할 때 어떤 방식으로 진행할 것인가?

 

1. 주사위 조합

조합의 경우 간단하게 파이썬 라이브러리인 combinations를 사용하였다. 주사위 숫자 배열을 미리 선언하고 주사위 숫자를 조합했다.

# 주사위의 숫자 배열을 선언한다.
dice_num = [i for i in range(n)]

# 조합을 사용하여 A의 리스트를 생성한다.
for a_dices in list(combinations(dice_num, n//2)):

 

2. 주사위 조합

가장 단순한 방식은 A의 주사위로 만들 수 있는 모든 수와 B의 주사위로 만들 수 있는 모든 수들을 비교하여 win, draw, lose를 구하고 그 중 win의 값이 최대인 것을 구하는 방식이다. 이렇게 진행하면 시간 초과가 날 가능성이 높다.

1. 주사위 선택 가짓수 = 최대 10C5 = 약 500
2. A와 B가 주사위의 모든 수의 갯수(K) = 최대 6^5 = 약 8000
3. A와 B가 단순하게 비교하면 이중 For문을 사용 -> O(K^2)

전체 경우의 수 = 500x (6^5)^2 = 3e10

 

 

주사위 합의 크기 부분에서 많은 시간을 썼다. 처음에 각 a, b의 합 리스트에 pivot을 옮겨가면서 승패를 구할 수 있을 것 같아 시도를 했지만, 너무 많은 시간을 소요했고 다른 방식으로 문제를 풀려고 했다. 

 

마지막으로 선택한 방식은 두 a, b의 합 리스트를 오름차순 정렬 후, a 합 리스트를 순회하면서 이진탐색을 통해 a리스트의 특정 수 i 가 b 리스트에 어디에 위치할 것인지를 파악하여 숫자를 비교하였다. 

 

        # 오름차순 정렬 -> 이분탐색 사용을 위해
        a_sums.sort()
        b_sums.sort()
        
        for i in a_sums:
            # 이진 탐색을 사용하여 i가 들어갈 위치를 찾는다.
            l_point = bisect_left(b_sums, i)
            r_point = bisect_right(b_sums, i)

            win += l_point
            draw += r_point - l_point
            lose += length - r_point

 

위와 같은 방식으로 win의 개수를 파악하였고, 여러 조합 경우의 수 중 최댓값에 해당하는 주사위 조합을 반환하는 방식으로 문제를 풀었다.

 

 

시간 복잡도

조합의 경우 최대 10C5 (약 500) 가지가 될 수 있으며, 코드 상에서 a와 b를 각각 정렬하는 부분에서 O(KlogK), A 리스트를 기준으로 이진탐색을 하는 과정에서 O(K) x O(logK) = O(KlogK) 가 걸린다. 따라서 전체적인 시간 복잡도는 O(M x KlogK) 이며 M(조합 경우의 수)의 최댓값이 500, K(리스트 경우의수) 의 최댓값이 8000 이므로 시간내에 동작한다.

코드

from itertools import combinations
from bisect import bisect_left, bisect_right


# 주사위 리스트를 입력받아서 만들 수 있는 합 조합 생성
def get_dice_sums(dice,dices, sum_list, index, total):
    if index == len(dices):
        sum_list.append(total)
        return

    for i in range(6):
        dice_num=dice[dices[index]][i]
        get_dice_sums(dice,dices, sum_list, index + 1, total + dice_num)


def solution(dice):
    n = len(dice)
    dice_num = [i for i in range(n)]
    half = n // 2
    answer = []
    max_win = 0
    
    for a_dices in list(combinations(dice_num, half)):
        b_dices = list(set(dice_num[:]) - set(a_dices))
        
        # A,B가 가진 주사위로 만들 수 있는 합을 모두 생성
        a_sums, b_sums = [], []
        get_dice_sums(dice,a_dices, a_sums, 0, 0)
        get_dice_sums(dice,b_dices, b_sums, 0, 0)


        # 오름차순 정렬 -> 이분탐색 사용을 위해
        a_sums.sort()
        b_sums.sort()
        
        # A를 기준으로 개수 파악
        win, draw, lose = 0, 0, 0
        length = len(b_sums)
        for i in a_sums:
            # 이진 탐색을 사용하여 i가 들어갈 위치를 찾는다.
            l_point = bisect_left(b_sums, i)
            r_point = bisect_right(b_sums, i)

            win += l_point
            draw += r_point - l_point
            lose += length - r_point

        if win > max_win:
            max_win = win
            answer = list(a_dices)

    answer=[i+1 for i in answer]
    return answer

 

 

회고

1. bisect 라이브러리를 어떻게 활용하는지 경험할 수 있었다.
2. 어떤 방식으로 풀지를 빠르게 판단하고, 밀어붙일 필요가 있다(고민만 하다가 늦어짐)