프로그래머스 level 2 예상 대진표

Problem

Solution

def solution(n,a,b):
    count = 0
    total_round = len(bin(n))-3
    
    left, right = 0, n
    
    while left < right:
        mid = (left + right) / 2
        if mid >= a and mid >= b:
            right = mid
        elif mid < a and mid < b:
            left = mid
        else:
            break
        count += 1
    
    return total_round - count

포화 이진 트리 구조를 응용하여 접근하였다.

이 포화 이진트리는 n=8일 때 발생하는 대진표이다. 즉 8, 9번 노드 중 승자가 4번 노드로 올라가는 식으로 생각하였다.
이 트리에서 8번, 10번이 각각 A, B라고 가정하였을 때 이 둘을 모두 포함하는 가장 작은 트리는 2번을 루트로 하는 트리이다.

즉, 3(전체 트리 깊이) - 1 (2번 노드의 깊이) = 2 를 얻을 수 있다.

이 과정을 이용하여 현재 트리의 범위를 left, right로 지정하여 depth를 올려가며 구하였다.

Reference

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