프로그래머스 팁스다운 : [예상 대진표] Java 문제 풀이 (재귀)

https://programmers.co.kr/learn/courses/30/lessons/12985?language=java

코딩테스트 연습 - 예상 대진표

하루에 한 경기 씩 진행되는 토너먼트에 참가한 전체 인원 2^^n명이 참가했습니다.

친구 A와 B의 시드 번호를 매개변수로 받고 A와 B가 몇일이 지나야 만날 수 있는지 day를 리턴해야됩니다.

토너먼트 방식

경기가 끝나고 다음 경기에 내가 몇번 순서인지 알 수 있는 방법이 있습니다.

토너먼트의 특성상 절반은 이기고 절반은 패배하기에 수는 항상 1/2로 줄어듭니다.

4번 선수는 두번째 경기에 2번이 되었고, 7번 선수는 다음 경기에 4번이 되었습니다.

A 선수를 4, B 선수를 7로 두었을때
A = A/2 + A%2입니다.

class Solution
{
    static int ans = 0;
    public int solution(int n, int a, int b)
    {
        if(a==b) return ans;
        ans ++;
        return solution(n,a/2 + a%2 , b/2 + b%2);
    }
}

재귀함수를 사용해서 A와 B가 같을때까지 A와 B 각각 몫과 나머지를 더한 값을 재귀함수로 구현하면

통과입니다.

한 천재의 코드

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

(A-1) XOR (B-1) 한 값을 이진 문자열로 변환한 값의 길이..