[프로그래머스] 주사위 굴리기(feat. Bisect Left 탐색에 관하여 간략하게)

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

프로그래머스

들어가며

개인적으로 애를 많이 먹은 문제이다.

해당 문제는 n의 갯수가 10개 이하로 느낌이 오듯이 완전 탐색 문제인 것을 확인할 수가 있다.

하지만 테스트 케이스 19번부터는 시간 초과가 발생하기에 효율성도 같이 신경을 써야한다.

문제 풀이 방법

1. 먼저, A와 B가 주사위를 반틈 나눠 가질 수 있는 경우의 수를 모두 한다. (combinations 라이브러리 사용)

2. 그리고 나눠 가진 주사위로 발생할 수 있는 모든 경우의 수의 합을 구한다. (product 라이브러리 사용)

3. A와 B의 경우의 수에서 각각을 완전 탐색하여 비교하지 말고 B만 정렬한 뒤, bisect left 탐색을 통해 A와 비교한다. (이기는 대상이 A이기 때문이다.)

4. bisect left 탐색으로 반환한 값은 해당 값이 이길 수 있는 값을 뜻하므로 이를 모두 더해서 가장 많이 이길 수 있는 경우를 답으로 반환한다.

풀이 코드

from itertools import combinations, product

def bisect_left(arr, target):
    left = 0
    right = len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
            
    return left

def solution(dice):
    answer = []
    maxv = -1
    
    for A_dice in combinations(range(len(dice)), len(dice)//2):
        count = 0
        B_dice = []
        for i in range(len(dice)):
            if i not in A_dice:
                B_dice.append(i)

        A, B = [], []        
        for i in product(range(6), repeat=len(dice)//2): # repeat를 작성하지 않으면 오류가 발생한다. 여러 파라미터들이 존재하기 때문
            countA, countB = 0, 0
            for j in range(len(i)):
                countA += dice[A_dice[j]][i[j]]
                countB += dice[B_dice[j]][i[j]]
            A.append(countA)
            B.append(countB)
        
        B.sort()
        
        for a in A:
            count += bisect_left(B, a)
        
        if count > maxv:
            maxv = count
            answer = list(A_dice)

    for i in range(len(answer)):
        answer[i] += 1
            
    return answer

 

Bisect left 탐색이란

bisect left 탐색은 정렬된 배열에서 목표값 이상인 첫 번째 요소의 인덱스로 반환하는 탐색 방법이다.

해당 문제에서는 몇 번째까지 이길 수 있는지 빠르게 구할 수 있기 때문에 시간 초과가 발생하지 않았다.

이진 탐색과 형태가 매우 유사하며, 매우 유사한 것이 큰 단점이다. (헷갈린다. 여기서 시간을 정말 많이 소모했다..)

하지만, 파이썬에서는 라이브러리를 친절하게 제공하기 때문에 앞으로는 라이브러리를 사용하도록 하자. (알았으면 진작 썼겠다 ㅠ)

지금은 알고리즘 풀이 시간이기 때문에 간단하게 작성하였지만 다음 시간에는 이에 대해서 조금 더 자세하게 작성해보도록 하겠다.

# 1. 라이브러리 사용
from bisect import bisect_left
mostLeftIndex = bisect_left(arr, target)

# 2. 직접 구현
def bisect_left(arr, target):
    left = 0
    right = len(arr) # 이때, len(arr)-1로 할 경우에 오답이 발생한다
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
            
    return left