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

문제 링크

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

프로그래머스

 

문제 설명

토너먼트로 형식으로 진행하는 대회가 있다. 대회는 N명이 참가하고, 각각 1 ↔ 2, 3 ↔ 4, N-1 ↔ N 번의 참가자끼리 게임을 진행한다. 매 라운드에서 이긴 참가자는 다시 1번부터 N / 2번을 차례대로 배정받는다. 

이 때, 처음 라운드에서 A번을 가진 참가자는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 문제이다. 

단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정한다.

제한사항

• N : 2 이상 2^20 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.) 

풀이

N의 값이 크기 때문에 규칙을 찾아야 한다고 생각했다. 규칙을 찾아보면, 대진표는 [1 2], [3, 4], [5, 6] 이런 식으로 붙게 되는데, 번호가 홀수 인지 짝수인지에 따라서 홀수일 때는, (번호 // 2) + 1 짝수일 때는, 번호 // 2 하여 자신의 번호가 1이 될 때까지 반복한다. 도중에 A와 B의 번호가 같아지는 경우 같은 라운드에서 만나게 된다. 

 

✅ Code - 성공

def solution(n,a,b):
    answer = 0
    
    while True:
        if a == b:
            break
            
        if a > 1:
            if a % 2:
                a = a // 2 + 1
            else:
                a = a // 2
                
        if b > 1:
            if b % 2:
                b = b // 2 + 1
            else:
                b = b // 2
                
        answer += 1
        
    return answer