프로그래머스 Lv2 예상 대진표 (python)

예상 대진표

풀이

처음에는 a와 b의 거리 차이로 풀려고 생각을 했어서 아래처럼 풀었다.

def solution(n,a,b):
    answer = 0
    value1, value2 = (a-1)//2, (b-1)//2
    quotient = 1
    for i in range(1, 21):
        if 2**i == n:
            quotient = i
            break
    if abs(value1-value2) + 1  > quotient:
        return quotient
    else:
        return abs(value1-value2) + 1

하지만 이러니 추가 테스트케이스로 8, 4, 5, 1의 경우에 틀리게 되어서 이 방법은 폐기하였다.

그래서 다른 방법을 시도하였다.
경기를 몇 번 뛰었는지를 확인하면 되는 것이기에 처음에 대진자와의 짝을 맞춰주기 위해 a-1, b-1을 해주었다.
그리고 while문을 돌려서 // 연산자를 이용하여 a//2 == b//2가 될 때까지 즉, 같은 대전을 할 때까지 반복하기로 했다.
이때 사용된 인덱스를 답으로 반환했다.

def solution(n,a,b):
    if (a-1) // 2 == (b-1) // 2:
        return 1
    i = 0
    a = a-1
    b= b-1
    while i <= 20:
        i += 1
        a = a // 2
        b = b // 2 
        if a == b:
            break
    return i

다른 사람 풀이

아래 방법은 내가 한 방법과 동일하나, -1이 아닌 +1을 이용했다.

def solution(n,a,b):
    answer = 0
    while a != b:
        answer += 1
        a, b = (a+1)//2, (b+1)//2

    return answer

그리고 아래 방법은 비트연산자를 이용한 방법을 사용했다.
a와 b에서 각 -1을 빼고 XOR 연산을 수행하여 두 비트가 다를 때만 결과가 1이 되게 만들어준다.
그리고. bit_length() 함수를 통해 1이 있는 제일 큰 위치 값을 반환해 준다.
이 방식으로 문제를 풀었다.
신기하다.

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