프로그래머스 : 예상 대진표

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

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

 

해결 방법 : 구현

• n이 $2^x$ 이면, 최대 x번째, 최소 1번째에 대진이 이루어진다.
• 이분된 특정 구간에서 a와 b가 가운데를 기준으로 양쪽에 있으면, 이 둘은 해당 구간 토너먼트에서 마지막에 만난다.
  • log2(n)으로 최대 경우를 얻고, a와 b가 분리될때까지 이분한다.
    • 이때 이분된 횟수에 따라 대진이 앞당겨지므로 answer -- 해준다.

import math

def solution(n,a,b):
    answer = math.log2(n) # 최대 경우
    a, b = min(a, b), max(a, b)
    mn, mx = 1, n
    
    while True:
        mid = (mn + mx) // 2 # 이분 구간
        if a <= mid < b: # a, b가 현재 구간 [mn, mx]에 대해 마지막에 만난다.
            return answer
        else: 
            answer -= 1
            if b <= mid:
                mx = mid
            else:
                mn = mid + 1