[Python] 프로그래머스 - 예상 대진표

https://programmers.co.kr/learn/courses/30/lessons/12985

코딩테스트 연습 - 예상 대진표

 

mid를 이분탐색으로 절반씩 옮겨가며, mid기준으로 같은쪽에 있으면 이분탐색을 계속 돌리고

서로 다른 쪽에 있으면 cnt를 출력하는 식으로 코드를 짰다.

import math
def solution(n, a, b):

    def binary_search(left, right, cnt):
        global answer
        # 이분 탐색
        if left > right:
            return cnt
        mid = (left + right) // 2
        # a와 b가 모두 mid보다 작거나 같으면 mid 왼쪽범위에서 이분탐색 실행
        if a <= mid and b <= mid:
            binary_search(left, mid, cnt - 1)
        # a와 b 모두 mid보다 크면 mid 오른쪽 범위에서 이분탐색 실행
        elif a > mid and b > mid:
            binary_search(mid, right, cnt - 1)
        # mid기준으로 a와 b가 반대쪽에 있으면 cnt가 answer
        else:
            answer = cnt
    
    # 초기 left, right, cnt값
    binary_search(0, n, math.log2(n))
    return answer

(프로그래머스 level: 2)