[Python] 프로그래머스 / 2024 KAKAO WINTER INTERNSHIP / 주사위 고르기

문제 링크

 

이거, 수학적으로 풀기 쉽지 않다.

 

문제를 보다보면 이건 마치 확률 및 통계 기법으로 풀릴 것처럼 보인다. 물론 솔직히 푸는 방법이 없을 것 같지는 않은데, 그거 수학적 풀이 생각하고 있느니 그냥 탐색하는 게 더 좋다. 그리고 해보면 알겠지만 수학적 풀이 구현이 더 어려움,,, 왜냐하면 문제 조건에서,

N <= 10 조건을 주면서 어디 마음껏 탐색해보라고 속삭이고 있기 때문이다. 세상에 N <= 10이라니, 이건 O(6^N)이라는 말도 안 되는 복잡도의 코드를 구현하라는 것과 같다. 

 

그럼에도 불구하고 시간복잡도 초과된 코드

아래의 코드는 brute-force 탐색 코드 치고 상당히 최적화가 잘 된 코드이다. 그럼에도 불구하고 시간복잡도가 초관된다. 어디 마음껏 탐색해보래서 진짜로 탐색했더니, 복잡도가 초과되는 것이다.

#시간복잡도가 초과된 정답코드

from itertools import combinations, product

def solution(dices):
    
    n = len(dices)
    
    perm = list(combinations(range(0, n), n//2))
    m = len(perm)
    best, best_choice = 0, None
    
    for i in range(m//2) :
        my_choice = perm[i]
        adversarial_choice = perm[m-1-i]
        
        my_available_scores = list(product(*[dices[j] for j in my_choice]))
        adversarial_available_scores = list(product(*[dices[j] for j in adversarial_choice]))

        my_possibility = 0
        adversarial_possibility = 0

        rest = 6 ** n
        for my_score in my_available_scores :
            for adversarial_score in adversarial_available_scores :
                rest -= 1
                if (a:=sum(my_score)) > (b:=sum(adversarial_score)) :
                    my_possibility += 1
                if a < b :
                    adversarial_possibility += 1
                    
                if my_possibility + rest < best and adversarial_possibility + rest < best :
                    break

        if adversarial_possibility > my_possibility :
            my_choice, adversarial_choice = adversarial_choice, my_choice
            my_possibility, adversarial_possibility = adversarial_possibility, my_possibility 

        if my_possibility > best :
            best = my_possibility
            best_choice = my_choice

    
    return sorted([x + 1 for x in best_choice])

 

정답 코드

이 Velog 포스트를 참고하였다. 여기서 알게된 것이 바로 bisect 모듈인데, 이것은 어떤 unseen 요소가 리스트 내에 만약 끼워넣어진다면 몇 번째로 sort될지를 O(log N)으로 알 수 있게 해주는 모듈이다. 백문이불여일견.

import bisect

# 정렬된 리스트
arr = [1, 3, 4, 7, 8]

# 숫자 5를 삽입할 위치 찾기
pos = bisect.bisect_left(arr, 5)
print(pos)  # 출력: 3

# 리스트에 5 삽입
bisect.insort_left(arr, 5)
print(arr)  # 출력: [1, 3, 4, 5, 7, 8]

 

물론 리스트의 초기 정렬은 별도로 진행해야 한다. *파이썬의 sort()는 O(N logN)임

 

bisect를 이용하면 조금 더 효율적으로 이 문제를 풀 수 있다.

from itertools import combinations, product
from bisect import bisect_left, bisect_right

def solution(dices):
    
    n = len(dices)
    
    perm = list(combinations(range(0, n), n//2))
    m = len(perm)
    best, best_choice = 0, None
    
    for i in range(m//2) :
        my_choice = perm[i]
        adversarial_choice = perm[m-1-i]

        my_available_scores = []
        adversarial_available_scores = []

        for product_choice in product(range(6), repeat=n//2) :

            sum_score = 0
            for j, k in zip(my_choice, product_choice) :
                sum_score += dices[j][k]
            my_available_scores.append(sum_score)

            sum_score = 0
            for j, k in zip(adversarial_choice, product_choice) :
                sum_score += dices[j][k]
            adversarial_available_scores.append(sum_score)

        adversarial_available_scores.sort()

        my_possibility = 0
        adversarial_possibility = 0
        
        for score in my_available_scores:
            wins = bisect_left(adversarial_available_scores, score)
            loses = len(adversarial_available_scores) - bisect_right(adversarial_available_scores, score)

            my_possibility += wins
            adversarial_possibility += loses

        if adversarial_possibility > my_possibility :
            my_possibility, adversarial_possibility = adversarial_possibility, my_possibility
            my_choice, adversarial_choice = adversarial_choice, my_choice

        if my_possibility > best:
            best = my_possibility
            best_choice = my_choice


    return sorted([x + 1 for x in best_choice])