대학원생이 쉽게 설명해보기

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

단순

def pickingNumbers(a):    
    m = [0] * 100    
    
    for num in a:
        m[num] += 1

    cnt = 0    
    for i in range(1,n):        
        cnt = max(cnt, m[i - 1] + m[i])
        
    return maxval

복잡

def pickingNumbers(a):
    # Write your code here
    _a = list(set(sorted(a)))
    cnt = -1
    
    subsets = []
    for i in range(len(_a)):
        temp = _a[i]
        subset = [temp]
        
        for j in range(i + 1, len(_a)):
            if abs(temp - _a[j]) <= 1:
                subset.append(_a[j])
                
        subsets.append(subset)
        
    for subset in subsets:
        _sum = 0
        
        for v in subset:
            _sum += a.count(v)
            
        cnt = max(cnt, _sum)
        
    return cnt

마방진 문제

def formingMagicSquare(s):
    # Write your code here
    s = [s[i][j] for i in range(3) for j in range(3)]
    mmatrix = []
    # 참고함
    for a in range(1, 10):
        for b in range(1, 10):
        	# 각 행, 열, 대각선의 합이 15가 되는 모든 경우의 수
            if set([a, 15-a-b, b, 5+b-a, 5, 5+a-b, 10-b, a+b-5, 10-a]) == set(range(1, 10)):
                mmatrix.append([a, 15-a-b, b,
                                      5+b-a, 5, 5+a-b,
                                      10-b, a+b-5, 10-a])
    result = sys.maxsize
    for m in mmatrix:
        cost = 0
        for i in range(9):
            cost += abs(m[i] - s[i])
        result = min(result, cost)
        
    return result

def catAndMouse(x, y, z):
    x = abs(x - z)
    y = abs(y - z)
    
    if x == y:
        return 'Mouse C'
    elif x < y:
        return 'Cat A'
    else:
        return 'Cat B'

def getMoneySpent(keyboards, drives, b):
     buy = -1
    
    for k in keyboards:
        if k < b:
            for d in drives:
                if k + d <= b:
                    buy = max(buy, k + d)
                
    return buy