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

시간초과 코드

def solution(n,a,b):
    answer = 0
    arr = [i for i in range(1, n+1)]
    
    while True:
        sub_lst = []
        for i in range(0, n, 2):
            if arr[i] == a and arr[i+1] == b:
                answer += 1
                return answer
            
            if arr[i] in [a, b]:
                sub_lst.append(arr[i])
                
            elif arr[i+1] in [a, b]:
                sub_lst.append(arr[i+1])
                
            else:
                sub_lst.append(arr[i])
                
        arr = sub_lst
        answer += 1
        n //= 2

    return answer

문제에 맞춰 로직을 그대로 구현 한 결과로 시간초과가 나게됨 (n의 범위가 배우 크므로 수식으로 접근 해야겠다 생각)

 

 

정답 코드

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

    return answer

해당 숫자들을 2씩 나눠가며 몫을 비교 한다.

처음엔 각 a, b에 1을 더하지 않고 비교를 했는데 그렇게 된다면 몫이 0이 될 경우가 생긴다.

(만약 a가 2일 때 2로 나누면 몫이 1이 되고, 그 이후 연산에서 몫이 0이 되므로 비교가 부정확 하다)