[Python] 주사위 고르기 (카카오 2024 겨울 인턴십 코테) 문제 풀이

 

프로그래머스 카카오 기출문제인

[주사위 고르기]를 파이썬으로 풀어보겠습니다!

 

이 문제는 다양한 경우의 수를 고려하여 최적의 경우를 고르는 문제로

다양한 itertools 함수를 사용할 예정입니다.

난이도는 Lv3로 답을 도출하는 건 쉽지만 시간 효율성을 고려해야 해서

조금 까다로운 문제였습니다!

 

 

프로그래머스

 

문제 설명

A와 B가 n개의 주사위를 가지고 승부를 합니다.

주사위의 6개 면에 각각 하나의 수가 쓰여 있으며

주사위를 던졌을 때 각 면이 나올 확률은 동일합니다.

각 주사위는 1 ~ n의 번호를 가지고 있으며

주사위에 쓰인 수의 구성은 모두 다릅니다.

A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다.

각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다.

점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.

A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.

 

입출력 예

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]]

            0번 주사위     /     1번 주사위     /     2번 주사위     /     3번 주사위

 

문제 풀이

입출력 예를 기준으로 풀이를 설명드리겠습니다.

dice가 총 4개 있기 때문에 A가 주사위 2개, B가 주사위 2개를 가집니다.

이때 A가 주사위를 가지는 경우의 수를 구하면 다음과 같습니다.

 

(0번 주사위 & 1번 주사위)

(0번 주사위 & 2번 주사위)

(0번 주사위 & 3번 주사위)

(1번 주사위 & 2번 주사위)

(1번 주사위 & 3번 주사위)

(2번 주사위 & 3번 주사위)

 

우리는 이걸 조합이라고 부릅니다.

파이썬에서는 itertools의 combinations를 쓰면 되겠네요.

cases = itertools.combinations(range(len(dice)), len(dice) // 2)
# [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

 

for case in cases 를 이용해 A의 경우의 수를 순회합시다.

이때 B는 A가 가진 주사위를 제외한 주사위를 모두 가지면 되겠죠?

for case in cases:
    a_case = list(case)
    b_case = [b for b in range(len_dice) if b not in case]

 

자 이제 A가 가진 주사위를 던질 때 나올 수 있는 숫자의 합을 전부 구하고,

B가 가진 주사위를 던질 때 나올 수 있는 숫자의 합을 전부 구해봅시다.

itertools의 product는 n개의 리스트에서 한 개씩 뽑아 만들 수 있는 경우를 모두 리턴하는 함수인데요.

A가 가진 주사위에서 한개씩 뽑아 그 눈의 수를 합치는 코드를 한 줄로 나타냈습니다.

(B도 동일하게 구할 수 있습니다.)

    # a가 날 수 있는 점수 list
    a_case_list = [dice[temp] for temp in a_case]
    a_scord_list = [sum(combination) for combination in itertools.product(*a_case_list)]
    print(a_scord_list)
    # [4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10]

    # b가 날 수 있는 점수 list
    b_case_list = [dice[temp] for temp in b_case]
    b_scord_list = [sum(combination) for combination in itertools.product(*b_case_list)]
    print(b_scord_list)
    # [2, 2, 5, 5, 6, 6, 4, 4, 7, 7, 8, 8, 4, 4, 7, 7, 8, 8, 5, 5, 8, 8, 9, 9, 5, 5, 8, 8, 9, 9, 5, 5, 8, 8, 9, 9]

 

다음은 A가 B를 이기는 경우를 구해봅시다.

이 부분에서 단순히 A와 B의 모든 경우를 순회하면서 체크하면 시간초과가 나게 됩니다ㅠㅠ

 

시간 효율성을 고려한다면 이진탐색 을 이용해 풀어야 되는데요.

itertools의 bisect를 이용할 수 있습니다!

    cnt = 0
    b_scord_list.sort()
    for a in a_scord_list:
        # b의 리스트에서 a가 어디에 있는지 확인 (비기는 것도 안되므로 bisect_left를 사용하)
        cnt += bisect.bisect_left(b_scord_list, a)

    if max_cnt < cnt:
        max_cnt = cnt
        result = [a+1 for a in a_case]

 

b의 점수 리스트에서 a의 점수를 찾아야 되기 때문에

b 점수 리스트를 오름차순 정렬한 후

a가 이길 경우의 수를 cnt 에 추가합니다.

 

최종적으로 a가 이기는 경우의 수가 앞서 구한 다른 주사위 조합보다 크다면

result를 갱신해 줍니다.

 

이렇게 하면 최종적으로 result만 반환하면 답이 도출되겠네요!

 

👇 아래 전체 코드 첨부합니다~!

def solution(dice):
    len_dice = len(dice)
    max_cnt = 0
    result = []
    dic = {}
    
    # 주사위를 가져갈 경우의 수
    cases = itertools.combinations(range(len_dice), len_dice // 2)
    for case in cases:
        a_case = list(case)
        b_case = []
        for b in range(len_dice):
            if b not in a_case:
                b_case.append(b)
            
        # a가 날 수 있는 점수 list
        a_case_list = [dice[temp] for temp in a_case]
        a_scord_list = [sum(combination) for combination in itertools.product(*a_case_list)]
        # print("a", a_scord_list)
        
        # b가 날 수 있는 점수 list
        b_case_list = [dice[temp] for temp in b_case]
        b_scord_list = [sum(combination) for combination in itertools.product(*b_case_list)]
        # print("b", b_scord_list)
        
        cnt = 0
        b_scord_list.sort()
        for a in a_scord_list:
            # b의 리스트에서 a가 어디에 있는지 확인 (비기는 것도 안되므로 bisect_left를 사용하)
            cnt += bisect.bisect_left(b_scord_list, a)
        
        if max_cnt < cnt:
            max_cnt = cnt
            result = [a+1 for a in a_case]
                    
    return result

 

(혹시 틀리거나 이해가 안 가는 부분이 있으시다면 댓글 남겨주세요~😉)