Github

예상 대진표

1. 개요

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번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

2-1. 문제 설명 - 제한사항

  • N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)

  • A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

2-2. 문제 설명 - 입출력 예

N
A
B
answer

8

4

7

3

2-3. 문제 설명 - 입출력 예 설명

입출력 예 #1

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

3. 문제 풀이

function solution(n, a, b) {
  let round = 1;
  // 1) a, b의 값을 비교하여 max 변수와 min 변수에 할당하기
  let max = a > b ? a : b;
  let min = a < b ? a : b;
  while (true) {
    // 2) a, b가 만나는 라운드라면 해당 라운드를 반화하기
    if (min % 2 === 1 && min + 1 === max) return round;

    // 3) max와 min이 다음 라운드에서 받게 될 번호를 구하기
    max = Math.ceil(max / 2);
    min = Math.ceil(min / 2);

    // 4) 반복문이 한 번 실행될 때 마다 round를 1올리기
    round++;
  }
}

a와 b 두 선수가 만나는 경우는 아래의 두 조건을 모두 만족해야 한다.

  • a의 변호가 홀수 일 때,

  • a + 1이 b일 때

위의 조건을 만족할 때 까지 반복문을 실행하였다.

1) a, b의 값을 비교하여 max 변수와 min 변수에 할당하기

let max = a > b ? a : b;
let min = a < b ? a : b;

a 선수와 b 선수가 라운드에서 만날 조건을 확인하기 위해 max 변수와 min 변수를 선언하여 각가 큰 값과 작은 값을 할당한다.

만약 이를 하지 않았다면 어떤 값이 더 큰지 몰라 반복문 내의 조건문이 더 복잡해 질 수 있다.

2) a, b가 만나는 라운드라면 해당 라운드를 반화하기

if (min % 2 === 1 && min + 1 === max) return round;

두 선수 중 작은 번호(min)이 홀수이고 그 다음이 바로 max라면 두 선수는 해당 라운드에서 만나기 때문에 해당 라운드를 반환한다. min이 홀수이여야 하는 까닭은 2,3는 각각 다른 선수와 대결을 하기 때문이다.

반복문에서 return를 실행하면 반복문을 종료할 뿐 아니라 해당 반복문이 실행된 함수도 return 값을 반환하며 종료한다.

3) max와 min이 다음 라운드에서 받게 될 번호를 구하기

max = Math.ceil(max / 2);
min = Math.ceil(min / 2);

max와 min이 다음 라운드에서 받게 될 번호를 구한다.

만약 번호가 13이라면 이를 2로 나누고 올림한 수인 7이다. 만약 번호가 1이라면 이를 2로 나누고 올림한 수인 1이다.

즉, 홀수인 경우 때문에 올림을 한다.

4) 반복문이 한 번 실행될 때 마다 round를 1올리기

round++;

반복문의 하나의 순회는 하나의 라운드이다. 그렇기 때문에 다음 순회로 가기 전에 round를 1올려야 한다.

결과

4. 다른 사람 풀이

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

  return answer;
}

위의 풀이를 보면 a와 b가 서로 같아질 때 까지 반복문을 실행한다. a와 b가 같다는 것은 둘이 대결을 바로 전 라운드에서 했다는 뜻이기 때문에 answer의 시작을 0으로 하고 굳이 나중에 리턴을 할 때 라운드에 -1를 하지 않는 것이 인상깊다.

결과

5. Conclusion

예상 대진표 문제도 어렵지 않게 풀었다. 두 선수가 만나는 조건만 잘 파악하면 코드 작성은 어렵지 않았다. 다만 나의 풀이에서 작은 값을 가진 선수가 홀수, 짝수 일 때의 경우를 조심해야 한다. 실제 코딩 테스트에선 테스트 코드는 통과할지 몰라도 실제 답안에선 틀린 경우가 등장할 수 있기 때문이다. 항상 예외 상황을 생각하며 문제를 이해하고 풀어보자.

📅 2022-09-28

PreviousN개의 최소공배수Next튜플

Last updated