문제

정답 코드

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;

        while (a!=b) {
            if (a % 2 == 1) a += 1;
            if (b % 2 == 1) b += 1;
            
            a/=2;
            b/=2;
            answer+=1;
        }
        return answer;
    }
}

토너먼트 진행시 /2 한 값이 다음 경쟁번호이기때문에 재귀호출하면 되는 문제였다.
풀고나니 n이 필요하진 않았다!

다른 사람 풀이

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;

        while (a!=b) {
            a = (a+1)/2;
            b = (b+1)/2;
            answer+=1;
        }

        return answer;
    }
}

스터디 팀원분의 코드인데, 더 간결해졌다.
이렇게 +1을 하고 바로 2로 나눠도 되겠구나!

다른 사람 풀이 2

class Solution
{
    public int solution(int n, int a, int b)
    {
        return Integer.toBinaryString((a-1)^(b-1)).length();
    }
}

진짜 이걸 어떻게 생각한거지..?ㅋㅋㅋ

• 비트연산자 ^ : 두 개의 비트가 서로 다른 경우에 1을 반환하는 XOR 연산

(예시)
4와 7일 때, -1씩 하면 3과 6 -> 11(2) XOR 110(2)이 되고 값은 "101"이 된다.
문자열 길이가 바로 3라운드로 출력 되는 것이다.

어떻게 이게 가능할까 생각해봤을 때...

1. 이해 해야 할 것

• 참가자 수 2의 n승에 따라 라운드 횟수(n)가 증가한다.
• 2의 x승을 2진수로 표현하면 x가 증가 될 때마다 자리수가 바뀌고, 그 자리수는 (x+1)이다.
• 만나는 라운드는 2의 n승을 전부 다 계산 할 필요 없이, 둘의 차이를 구하면 된다.
• 가까운 번호일수록 2진수의 앞자리가 겹친다.

2. 문제를 풀 때

• 반으로 나눈 뒤쪽은 2진수의 자리수 크기가 같은 애들끼리만 만난다.
  (이 때 앞쪽의 맨 뒷번호는 뒤쪽과 자리수가 같기 때문에 제외해야하므로 -1을 모두 적용: 어짜피 자리수를 구할거라 결과에는 영향 없음)
• 비트연산으로 둘이 겹치는 2진수의 자리(불필요한 라운드) 제거
• 2진수의 자리수 = 라운드의 수

이걸 어떻게..?? 그림으로 그려놓고 2진수를 나열한 뒤 한참 보고서야 알았다.