[Programmers/ level2] 예상 대진표
👩문제
△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, … , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.
이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.
👩제한사항
- N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
- A, B : N 이하인 자연수 (단, A ≠ B 입니다.)
👩입출력 예
| N | A | B | answer |
|---|---|---|---|
| 8 | 4 | 7 | 3 |
🙄입출력 예 설명
- 예제 #1
- 첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.
🙋♀️내 풀이
나는 A와 B가 언제 붙게 될까에 초점을 두었다.
N= 8, A = 3, B = 6인 상황을 가정해보자.
-
3과 6이 서로 붙기 위해서는 위의 그림과 같이 결승까지 가야한다. 따라서 결과는 3이 된다.
-
그렇다면 A, B가 결승 전에 붙을 수 있는 경우는 언제일까??
- 위의 상황에서는 결승 전 4명씩 토너먼트를 진행하므로 A,B가 1-4 사이에 존재하거나 5-8 사이에 존재해야 한다.
- 또, 1-2, 3-4, 5-6, 7-8 사이에 각각 존재한다면 가장 첫 번째 경기에서 만나게 될 것이다.
🙄 여기까지 살펴본다면 🔔A,B가 어디에 위치하냐🔔가 키가 되는 것을 알 수 있다.(너무 복잡하게 설명한 것 같다!희희!)
그렇다면 코드를 바탕으로 나머지 풀이가 어떻게 이루어지는지 살펴보자!
def solution(n,a,b):
while 1:
n /= 2
if a > n and b > n:
a -= n
b -= n
elif not(a <= n and b <= n):
return int(n*2-1).bit_length() #2의 몇 승인지 구함
- 두 수 모두 N/2보다 크다면 범위를 절반으로 좁힌 곳에서 다시 각각 어디에 위치하는 지를 반복해서 살펴본다.
- 절반으로 범위를 줄이기 때문에 a,b에서 각각 n/2 값을 빼준다.
- 하지만 두 수다 N/2보다 작다면 굳이 빼주지 않아도 줄인 범위 내에서 탐색이 가능하다.
- a, b 값이 하나는 N/2보다 크고, 하나는 작거나 같다면 결국 N명의 토너먼트 중 결승에서 만나게 된다. 따라서 결승이 몇 번째에 이루어지는 지가 답이 된다.
- 이는 총 두명일때도 적용이 된다. (2/2 = 1이므로 한 명은 N/2보다 작고, 한 명은 N/2보다 크게 된다.)
🙋♀️best 풀이 : 다음 라운드에서 배정받는 번호로 풀이!
🙄 어쩌면 이 방법이 가장 올바른 풀이라고 생각이 된다. 내 코드는 이 방식을 돌고돌아 해결한 느낌이다…ㅎㅎ
def solution(n,a,b):
while a!=b:
answer += 1
a, b = (a+1)//2, (b+1)//2
return answer
🙄위 풀이는 아래 사진을 통해 아마 쉽게 이해할 수 있을 것이다.
- 다음 라운드에서 배정받을 번호는 2로 나눔으로써 알 수 있다.
- 이때 올림 값이 배정받는 번호이므로 계산을 간편하게 하기 위해 a+1, b+1로 계산한다.
- 두 값이 같아지면 붙었다는 의미이므로 값이 같아지기 직전까지 계산을 반복한다.
어떤가! 정말 간단하고, 명확한 풀이지 않은가! 그렇다면 또 다른 풀이를 하나 더 살펴보자!
🙋♀️다른 풀이 : 이진코드로 풀이
def solution(n, a, b):
return ((a-1)^(b-1)).bit_length()
🙄처음 봤을 때 잘 이해가 가지 않았던 코드이다. 계속해서 2로 나누는 방식이 아닌 2가 곱해질 때마다 자리수가 늘어나는 이진코드로 풀었다는 점이 너무 신박했다!
- 해당 숫자의 이진코드의 자리수 - 1는 해당 숫자가 1이 되기 위해서 2로 나누어야 하는 횟수를 의미한다.
- 이진코드의 첫 번째는 0과 1을 나타내는 자리이므로 이를 제외시키기 위해 -1을 작업한다.
- 이는 결국 🔔해당 수가 결승에 도달하기까지 거쳐야 할 경기의 수🔔로 해석할 수 있다.
- a, b의 값의 차이가 적을 경우, 이진코드의 상위 비트가 비슷한 형태를 띄게 된다. 반대로 a, b의 값의 차이가 많이 날 경우, 이진코드의 상위 비트가 다른 형태를 띄게 된다.
- 동일한 상위 비트는 결승을 가기 전, 이미 둘이 붙어 한 명이 올라간 경우이므로 서로 다른 비트의 길이가 만나게 되는 지점이다.
🙄 해당 코드를 이해했지만 말로 설명하는 것이 어려웠다..ㅜ
🙋♀️알게된 점
- bin(정수)를 통해 이진코드를 구할 수 있다.
- bit_length()를 통해서 이진코드의 길이를 구할 수 있다.
🙇♀️풀이에 부족한 부분이 있다면 말슴해주세요! 감사합니다!
댓글남기기