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

문제

풀이

 문제에서 요구하는대로 풀었다가는 시간초과가 나오는 문제이기에 조심해야 한다. 문제를 풀어보려다 결국 풀리지가 않아 다른 블로그 글을 참고 하였다.

 

 내가 기존에 풀었던 방법은 모든 참가자들끼리 시합을 벌여서 임의의 참가자들 다시 대진표에 넣는 방식을 사용했다.(마치 큐처럼) 그러나 올바른 풀이는 모든 참가자들의 시합을 벌이는것이 아니라 관심있는 참가자들만 시합을 진행시켰다.

풀이는 아래와 같다

-  1번과 2번 참가자의 번호를 /2 하면 몫은 1과 0이다.

- 3번과 4번 참가자의 번호는 /2하면 몫은 1과 0이다.

 

그렇다면

- 1번과 2번 참가자의 번호에 +1을 하여서 /2를 하면 몫은 1, 1이다.

- 3번과 4번 참가자의 번호에 +1을 하여서 /2를 하면 몫은 2, 2이다.

 

즉 해당 참가자 번호에서 +1을 한 후 /2를 하면 다음 라운드에서 얻게 되는 참가자 번호와 같다.

그 말인 즉슨 계산을 반복하다 각 참가자들의 번호가 같다면 이전 라운드에서 서로 시합을 진행했다는 말이 되므로 몇번째 라운드에서 시합을 했는지 알 수 있다.

 

코드

def solution(n,a,b):
    answer = 0

    while a!=b:
        a = (a+1)//2
        b = (b+1)//2
        answer = answer+1

    return answer