✨ Lv. 2 - 예상 대진표
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12985
문제 설명
△△ 게임대회가 개최되었습니다. 이 대회는 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 입니다.)
풀이 코드 + 설명
정말 오랜 기간동안 고민해본 문제였습니다. 분명 단순한 문제인데 이렇게도 안풀릴 수 있나... 싶었는데 답을 알고 나니 허무할만큼 간단한 문제였습니다.
계속해서 시도했던 풀이법은 직접 대진표에서 줄여나가며 언제 해당 숫자들이 만나게 되는지를 반복하는 방식이였습니다. 이는 코드가 너무 복잡해지기도 하고 그리 좋은 풀이법도 아니었습니다. 반대로 참가자의 번호를 직접 변경하면 어떨까 하는 생각에서 다음과 같은 풀이법을 떠올릴 수 있습니다.
| 라운드 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 |
| 2 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 |
| 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
위와 같이 각 라운드마다 이긴 선수에게 새로운 번호를 순서대로 부여하는 방식입니다. 1번 선수와 2번 선수가 게임을 진행해 이긴 선수에게는 1번을, 3번 선수와 4번 선수가 게임을 진행해 이긴 선수에게는 2번을...
계속 반복하다보면 숫자가 서로 같아지는 지점이 존재할 것이고, 바로 그 경우에서의 라운드가 우리가 구하고 싶은 결과값이 됩니다. 예시로 만약 A = 4, B = 7일 경우에는 두 수가 같아지는 지점이 3라운드이므로 결과값은 3이 됩니다.
그렇다면 매 라운드마다 새로 부여하는 번호는 어떻게 부여해야 할까요? 이는 이전에 가지고 있던 선수의 번호를 2로 나눈 값을 올림하면 쉽게 해결할 수 있습니다. 이를 바탕으로 코드를 아래와 같이 작성할 수 있습니다.
function solution(n, a, b) {
let result = 0;
while(a !== b) {
a = Math.ceil(a / 2);
b = Math.ceil(b / 2);
result++;
}
return result;
}
