[프로그래머스] Lv2. 예상 대진표

문제

대략 백만개의 숫자가 있지만 토너먼트 형식이기 때문에 총 라운드 수는 최대 20번

풀이

💡 아이디어

매 라운드마다 이긴 숫자들만 모아둘 리스트를 만들어서 만날 때까지 반복하면 되지 않을까 했는데 A와 B가 아닌 다른 숫자들을 굳이 저장해둘 필요가 없을 것 같아서 다른 방식을 떠올렸다

일단 1 2 3 4 5 6 7 8 이렇게 토너먼트가 이뤄진다면 4는 2번째 그룹, 7은 4번째 그룹에 속하게 된다. A와 B가 속할 그룹의 번호만 알 수 있다면, 그 번호가 같아질 때 둘은 토너먼트 경기에서 만나게 되는 것이다.

그룹을 구하는 방법은 2로 나눠주면 된다. 하지만 1 2 3 4 의 경우 2로 나눠서 몫을 구하면 0 1 1 2 로 (1) (2, 3) (4, 5) 이런식으로 그룹이 이뤄지게 된다. 이를 해결하기 위해서는 A와 B를 처음에 -1씩 해주면 된다.

계산마다 +1을 해주는 방법도 있지만 굳이 매 계산마다 더해줄 필요 없이 시작전에 한 번만 빼주고 시작을 했다

def solution(n,a,b):
    a -= 1
    b -= 1

    num = 1
    while True:
        a //= 2
        b //= 2
        
        # a와 b가 경기에서 만나게 되면 횟수 출력
        if a == b:
            return num
        num += 1