[HackerRank-python] Climbing the Leaderboard

binary search는 동일하게, 같은 숫자가 나온 시점에서(예를 들어, 30이 있는 배열에서 30을 삽입하고 싶을때) 왼쪽으로 갈지(start == mid), 오른쪽으로 갈지(mid + 1 == end)의 차이

1. bisect_right

def climbingLeaderboard(ranked, player):
    # Write your code here
    def bisect_right(arr, value, start, end):
        if start >= end:
            return start
        
        mid = start + (end - start) // 2
        
        if value < arr[mid]:
            return bisect_right(arr, value, start, mid)
        else:
            return bisect_right(arr, value, mid + 1, end)
        
    ranked = sorted(list(set(ranked)))
    
    ranks = []
    len_ = len(ranked)
    for score in player:
        rank = len_ - bisect_right(ranked, score, 0, len_) + 1
        ranks.append(rank)
        
    return ranks

arr = [10, 20, 30, 40, 40, 50, 60, 70] 일때,

# mid, 선택된 arr
4 [10, 20, 30, 40, 40, 50, 60, 70]
6 [50, 60, 70]
5 [50]
5

2. bisect_left

def bisect_left(arr, value, start, end):
    if start >= end:
        return start

    mid = start + (end - start) // 2

    if arr[mid] < value:
        return bisect_left(arr, value, mid + 1, end)
    else:
        return bisect_left(arr, value, start, mid)

arr은 동일,

# mid, 선택된 arr
4 [10, 20, 30, 40, 40, 50, 60, 70]
2 [10, 20, 30, 40]
3 [40]
3