문제 설명
△△ 게임대회가 개최되었습니다. 이 대회는 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 : 2^1 이상 2^20 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
- A, B : N 이하인 자연수 (단, A ≠ B 입니다.)
입출력 예
| N | A | B | answer |
|---|---|---|---|
| 8 | 4 | 7 | 3 |
풀이
from math import log, ceil
def solution(n, a, b):
for num_of_round in range(1, int(log(n, 2)) + 1):
if a % 2 and b == a + 1:
return num_of_round
elif b % 2 and a == b + 1:
return num_of_round
a = ceil(a / 2)
b = ceil(b / 2)해결 과정
반복 횟수
while True로 무한 반복을 돌려서 해결할 수도 있지만, 반복 길이를 명시할 수도 있다. n번의 경기 참여자가 있다면 최대 int(log(n, 2))번 라운드 내에서 A, B가 서로 만나게 된다.
n = 8을 예로 들어보면 8명일 때, 4명일 때, 2명일 때로 최대 3번 라운드가 진행된다. 이 값은 2 ^ 3 = 8이라는 식에서 지수인 3에 해당한다.
정답 조건
A, B의 번호가 홀수고, 나머지 번호가 자신 + 1의 값이라면 서로가 대전 상대이므로 해당 조건을 만족할 때 라운드 수를 반환했다.
ceil
python의 round 함수에는 일반적인 반올림과는 다른 규칙이 적용된다. 자세한 내용은 이 글의 댓글을 참고하자.
그래서 해당 문제를 해결하고자 ceil 함수를 통해 값을 감소시켰다. 올림이라고 해도 X.0은 X로 나오기 때문에 가능한 것이다.
다른 사람의 풀이
하지만, 문제를 풀고 다른 사람의 풀이를 보니 나는 아직 멀었다는 생각을 할 수밖에 없었다. 아직도 갈 길이 멀은 것 같다.
def solution(n,a,b):
return ((a-1)^(b-1)).bit_length()처음에 이 풀이를 보고 정말 놀랐다. 이런 생각을 나온다는 것 자체가 정말 신기했다.
이 풀이는 비트 XOR 연산을 이용하는 방식이다. 값의 차이가 멀 수록 상위 비트에서 XOR의 값이 1로 나오게 되기 때문에 큰 값이 나오게 되는데, 이 값의 길으를 반환하는 것이다.
이때, a와 b의 값을 1씩 줄여 XOR 연산할 때 문제 정답을 구할 수 있도록 했다는 것도 좋은 센스였다.
def solution(n,a,b):
answer = 0
while a != b:
answer += 1
a, b = (a+1)//2, (b+1)//2
return answer(a + 1) // 2, 이 방식이 굉장히 좋았다. 나는 어떻게 하면 그 상태에서 값을 내릴 수 있을까를 생각했는데, 1을 더하고 // 2를 하면 정수 형태로 반환되기 때문에 짝수의 경우든 홀수의 경우든 원하는 번호로 할당이 된다.
또한, 이렇게 되는 경우 7, 8의 번호가 4, 4가 되면서 같은 값이 되므로 같을 때 해당 라운드 수를 반환해주면 된다.
