[프로그래머스] 예상 대진표 (TypeScript로 풀기)

문제 설명

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

---

문제 풀이

첫 while문을 통하여 전체 라운드가 몇 라운드 진행되는지 확인을 하여 answer을 증가시켰습니다.

총 answer만큼의 라운드가 진행될 것입니다. 그전에 만나는 경우를 찾기 위하여 두 번째 while문을 돌립니다. 토너먼트는 제일 위에서부터 참가자 수의 절반을 기준으로 중앙값보다 왼쪽은 작은 수 오른쪽은 큰 수가 위치 하여 a와 b가 같이 n의 반 보다 작은 경우 혹은 큰 경우 한 라운드 빨리 만날 수 있습니다.

따라서 조건에 만족하면 answer를 하나 줄이게 됩니다. 단 a와 b가 중간값보다 큰 경우는 n/2만큼 번호를 차감시켜야 1부터 n/2까지의 숫자로 대진표가 새로 작성됩니다.

이렇게 n이 2가 될 때까지 반복을 돌리다가 a와 b가 중앙값을 기준으로 양쪽에 위치하게 된다면 더 빨리 만날 방법이 없기 때문에 break로 빠져나오게 됩니다.

function solution(n: number, a: number, b: number) {
  let answer: number = 0;
  let player: number = n;
  while (player > 1) {
    player /= 2;
    answer++;
  }
  while (n > 1) {
    if (n / 2 < a && n / 2 < b) {
      a -= n / 2;
      b -= n / 2;
      n /= 2;
      answer--;
    } else if (n / 2 >= a && n / 2 >= b) {
      n /= 2;
      answer--;
    } else {
      break;
    }
  }
  return answer;
}

다른 사람의 풀이를 보고 이러한 방법이 있었구나 하여 typescript로 변경하여 추가로 작성합니다.

문제에서 라운드에서 이긴 경우 왼쪽부터 다시 1, 2, 3,..., n으로 번호를 부여한다고 한 것이 큰 힌트였던 것 같습니다. 

본인이 이기게 된다면 새로 부여받는 번호는 기존 자신의 번호를 2로 나누고 올림을 하면 새로 받을 번호가 됩니다. 따라서 a와 b가 경기가 끝난 후 같은 번호가 부여되는 경우는 a와 b가 경기를 한 경우이므로 아래와 같이 a와 b가 다른 경우 반복을 하게 될 것이고 반복할 때마다 한 라운드씩 올라갔으므로 answer을 증가시킵니다. a와 b가 동일하다면 경기를 치른 것이기에 반복을 끝내고 answer을 반환합니다. 

function solution(n: number, a: number, b: number) {
  let answer: number = 0;
  while (a !== b) {
    a = Math.ceil(a / 2);
    b = Math.ceil(b / 2);
    answer++;
  }

  return answer;
}