[파이썬] 프로그래머스 예상 대진표 풀이

문제 확인

프로그래머스

나의 풀이

• 전체 대진표는 대결하는 두 쌍($0, 1$)과 순서로 표현할 수 있다.
• 순서는 숫자를 2 로 나눴을 때 몫으로 표현할 수 있기 때문에, $a$와 $b$가 몫이 같을 때 까지 라운드를 반복하면 된다.

# 0 1 2 3 4 5 6 7
# 0 1 2 3
# 0 1
def solution(n,a,b):
    # 1 라운드부터 시작하기 때문에
    answer = 1
    # 몫 정보로 대결 여부 파악할 수 있도록 변경
    # 몫이 같다면 둘이 매칭된 것
    a, b = a - 1, b - 1
    while a // 2 != b // 2:
        a //= 2
        b //= 2
        answer += 1
    return answer

다른 사람 풀이

신기한 방법으로 풀었는데, 딱히 설명이 없어서 이해를 100 % 했는 지는 모르겠다. 

나름 내가 이해한 방법을 적으면 아래와 같다.

def solution(n,a,b):
    return ((a-1)^(b-1)).bit_length()

• 대결 대상자가 만나려면 그 둘이 1개의 비트로 표현할 수 있는 $(0, 1)$에 위치해야 한다.
• 대결을 반복하면서 점점 $2$ 씩 줄어드는 것은, 결국 비트가 줄어드는 것으로 생각할 수 있다. 
• 대결 대상자에 대해 XOR 연산을 하여 떨어진 정도를 수치화했다.
• 1 번의 대결 마다 비트가 1개 씩 줄어들기 때문에, 라운드 횟수는 '떨어진 정도'를 이진수로 표현 했을 때의 길이로 생각할 수 있다.

프로그래머스