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

🗓️ 문제 설명

• ㅇㅇ게임 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다.
• N명의 참가자는 각각 1부터 N번을 차례대로 배정받고, N-1번과 N번의 참가자끼지 게임을 진행합니다.
• 각 게임에서 이긴 사람은 다음 라운드에 진출하고, 다음 라운드에 진출할 참가자의 번호는 다시 1부터 N/2번을 차례대로 배정받으며 게임은 최종 한 명이 남을 때까지 진행됩니다.
• 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 반환하세요.
• 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.
• 제한 사항
  • N : 2¹ 이상 2²⁰ 이하인 자연수
  • A, B : N 이하인 자연수(A ≠ B)
  • 부전승은 발생하지 않음
• 입출력 예시

N	A	B	answer
8	4	7	3

 

💻 코드

최종 코드

 

코드 풀이

 

다른 사람 풀이

풀이 1번

• ^ : XOR 연산으로 2진수인 두 수의 각 자리수가 서로 다른 값을 가질 때, 1을 반환합니다.
  • 예시) 문제의 입출력 예시인 4와 7을 예로 들면 4의 이진수는 '100', 7의 이진수는 '111'이기 때문에, 4^7은 '011'인 3을 반환하게 됩니다. 
• bit_length() : 2진수의 길이를 반환하는 함수입니다.
• 풀이 해석
  • 아래의 이미지는 N=8인 경우의 대진표입니다. 만일 a = 4, b = 7 인 경우를 살펴보면 a^b는 3(11)이 나옵니다. 그래서 bit_length()를 적용하게 되면 2가 반환됩니다. 하지만 (a-1)^(b-1)을 하면 5(101)이 나오기 때문에 bit_length()를 적용하면 3이 반환됩니다.