[Lv.2] 예상 대진표

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 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 입니다.)

풀이

이 문제는 2가지 방식으로 풀 수 있다. 첫 번째 방법은 단순히 무식하게 재귀를 이용하는 것이고, 두 번째 방법은 a와 b를 기준으로 2씩 나누며 거꾸로 올라가는 방법이다.

나는 처음에는 단순히 무식하게 재귀로 풀어버렸다... 일단 n은 8, a는 4, b는 7이라고 가정했을 때
1 2 3 4 5 6 7 8 -> 1 4 5 7 -> 4 7 이렇게 총 3라운드만에 만나게 된다. 이것을 보고 처음 배열을 하나 담고 만날때까지 재귀를 돌리는 방법이 떠올랐다. 그래서 재귀를 이용해 풀기는 했지만 계산 시간이 굉장히 오래 걸리는 코드였다.

그래서 다른 사람 풀이를 봤는데 엄청 간단하게 푼 코드가 있었다. 그 방식이 바로 while문을 이용해 a와 b를 2씩 나누며 1이 될때까지 카운팅을 해주면 끝인 거였다... 나는 왜이리 어렵게 생각해서 풀었을까...쩝...아쉬운 문제였다

통과 코드

// 재귀
function solution(n,a,b) {
  return search(Array(n).fill().map((v,i)=>i+1), a, b, 1);
}
 
function search(array, a, b, num) {
  // 1 2 3 4에서 2와 3일때는 라운드를 1번 더 가야함
  if ((
    array.indexOf(a) - array.indexOf(b) === 1 && array.indexOf(b) % 2 == 0
  ) || (
    array.indexOf(b) - array.indexOf(a) === 1 && array.indexOf(a) % 2 == 0
  )) {
    return num;
  }
  var new_table = [];
  for (var i = 0; i < array.length / 2; i++) {
    if (array[i * 2 + 1] === a || array[i * 2 + 1] === b) {
      new_table.push(array[i * 2 + 1]);
      continue;
    }
    new_table.push(array[i * 2]);
  }
  return search(new_table, a, b, num + 1);
}
 
 
// while문: a와 b를 시작으로 2씩 나누며 카운팅만 해줌
function solution(n, a, b) {
  let answer = 0;
  while (a !== b) {
    a = Math.ceil(a / 2);
    b = Math.ceil(b / 2);
    answer++;
  }
 
  return answer;
}