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

링크

나의 코드

class Solution
{
    public int solution(int n, int a, int b)
    {
        int newA = (a / 2) + (a % 2);   // A가 승리시의 대진 번호
        int newB = (b / 2) + (b % 2);   // B가 승리시의 대진 번호

        // 다음 대진번호가 같아지면, 지금 만났다는 의미
        if (newA == newB)
            return 1;   

        // 아직 만나지 못했다면 다음 대진으로 이동 (재귀)
        return 1 + solution(n/2, newA, newB);
    }
}

기본 예제 (n = 8, a = 4, b = 7)을 기준으로 보았을 때, 다음 대진 번호는 (a / 2) + (a % 2)의 형태로 정해진다. 처음에는 단순히 a와 b의 차이가 1일 때 만났고 판단했지만, 이럴 경우 (n = 8, a = 4, b = 5)의 경우 답은 3이지만 1로 끝나버린다. 이를 해결하기 위해, 둘이 만나더라도 다음 대진번호를 만들어 조회했다.
다음 대진번호가 같아졌다는 뜻은 둘이 만나서 둘 중 한명이 이긴다는 의미이기 때문이다.
이를 재귀문으로 반복하여 결과를 만들었다.

이 재귀문은 n을 입력받아 사용하는 의미가 전혀 없는 코드다.

모범 답안

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

아직도 갈 길이 멀다.. 예시를 해당 로직대로 진행시켰을 때 답이 나오는 건 알겠으나, 원리 이해에 다분한 노력이 필요하다.

기존 문제는 번호가 1n까지 시작한다. 하지만 여기서 1만 빼주면 0(n-1)까지로 수의 범위를 줄일 수 있고, 둘이 대진에서 만났을 때를 내가 작성한 코드처럼 불편하게 하지 않고 (a/2) == (b/2)의 형태로 줄일 수 있다.
이것을 계산하는 형태로 binary를 이용했다. (a-1)^(b-1)을 통해 두 수의 몫이 같아지는 지점을 찾아냈다. 기본 예제 대입시, (3-1)^(7-1) = 4가 나온다.

기본식 : (a - 1) ^ (b - 1) =>
2진수 표현 : (101 - 1) ^ (111 - 1) =>
값 계산 : (100) XOR (110) =>
2진수 결과 : 100

여기서 2진수는 자릿수마다 /2, *2를 하여 오르고 내릴 수 있다. 두 수가 만나는 지점이 1이 있는 위치이기 때문에, Integer.toBinaryString()을 통해 만들어진 문자열 "100"의 .length()인 3을 결과값으로 반환한다.

위의 코드를 보니 갈 길이 너무 멀다..
어떻게 효율적으로 문제를 풀 것인가에 대해 더 공부해야겠다..