[ 프로그래머스 ] 12985 예상 대진표

📌 Problem

경기에는 총 N명의 참가자가 있으며 토너먼트 방식으로 경기가 진행된다. 1, 2번 선수, 3, 4번 선수 ... n-1, n번 선수가 짝을 이루어 경기를 치루고 이긴 사람이 다음 라운드로 나간다. 다음 라운드에서는 1, 2번 중 이긴 선수와 3, 4번 중 이긴 선수가 짝을 이루어 경기를 치룬다. 이런 방식으로 경기가 진행될 때 a번 선수와 b번 선수가 몇 번째 라운드에서 짝을 이루어 경기를 치룰 수 있는지 구하면 된다. 이때 a와 b는 둘이 경기를 치루기 전까지 무조건 이긴다고 가정한다.

📌 Solution

N번째 선수가 경기에서 이기면 다음으로는 (N + 1) / 2 번째 선수가 되어 다음 라운드를 진행한다. 이를 이용하여 a와 b 선수의 다음 라운드 번호를 계산한다. 또한 한 라운드에서 두 선수가 붙기 위해서는 두 선수의 번호 차이가 1이 되어야 하고 더 작은 번호를 가진 선수가 홀수이어야 한다.

📌 Code

public int solution(int n, int a, int b) {
    for(int round = 1; round <= Math.log(n) / Math.log(2); round++) {
        if (Math.abs(a - b) == 1 && Math.min(a, b) % 2 == 1) return round;
        a = (a + 1) / 2;
        b = (b + 1) / 2;
    }
    throw new RuntimeException("The game is over");
}