프로그래머스 12985 : 예상 대진표 - Javascript

문제 설명

• 출처: 프로그래머스 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 : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

입출력 예

• 예제 #1 첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

풀이 과정 - 시도 1 : 실제로 라운드 진행 (성공)

가장 단순하게 주어진대로 모든 라운드를 직접 진행해 결과를 찾는 방식으로 구현했습니다. 굉장히 비효율적이지만 실제로 잘 작동하고, 테스트 케이스도 모두 통과했습니다.

function solution(n, a, b) {
  //대진표 작성
  //a와 b는 1, 나머지는 0으로 저장
  const table = [];
  for (let i = 0; i < n; ++i) {
    table[i] = Number(a - 1 === i || b - 1 === i);
  }
 
  //0부터 n까지의 대진표를 순회한 후 n을 반으로 나누며 반복 진행
  let round = 0;
  for (let i = n; n > 1; n /= 2) {
    round++;
 
    //라운드 결과는 덧셈으로 간단하게 계산
    for (let j = 0; j < n; j += 2) {
      table[j / 2] = table[j] + table[j + 1];
 
      //라운드 결과가 2인 경우 a와 b가 만난 것이므로 라운드를 반환
      if (table[j / 2] === 2) {
        return round;
      }
    }
  }
}

:::info $n=8, a=4, b=7$ 의 경우 진행 방식

(table 배열의 1은 각각 a와 b를 의미합니다)

:::

풀이 과정 - 시도 2 : A와 B를 2로 나누며 비교

시도 1의 방식에서는 라운드가 진행 될 때마다 배열이 반으로 줄어들긴 하지만 의미없는 0값들에 대한 연산이 반복되기 때문에 굉장히 비효율적입니다. 사실상 모든 0은 의미가 없는 값이기 때문에 배열없이 효율적으로 a와 b만 이용해 라운드 값을 찾을 방법을 고민해봤습니다.

먼저 시도1에서 a와 b가 포함되지 않은 모든 라운드 계산이 의미가 없기 때문에 생략할 필요가 있습니다. 이를 위해 a와 b가 어떻게 이동하는지를 파악해보면 아래와 같습니다.

:::info $n=8, a=4, b=7$ 의 경우 a와 b의 인덱스 변화

:::

a와 b가 라운드가 진행 될 때마다 2로 나눈 값의 올림으로 변경되고, 이 값이 같아질 때 라운드 결과를 반환하게 된다는 것을 파악했습니다. 그 후 이 방식대로 작동하도록 수정해 코드를 개선했습니다.

그 결과 테스트 케이스 실행 시간이 평균 11.92ms에서 0.04ms로 월등히 빨라졌습니다. 또한, 배열을 사용한 탓에 27~34번 테스트케이스에서 메모리 사용량이 30메가 더 증가하던 증상이 사라졌습니다.

function solution(n, a, b) {
  let round = 0;
  while (a !== b) {
    //a와 b가 같아질 때까지 반복
    round++; //라운드 진행
 
    //a와 b를 2로 나누고 올림
    a = Math.ceil(a / 2);
    b = Math.ceil(b / 2);
  }
  return round;
}