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

-Code

class Solution {
    public int solution(int n, int a, int b) {
        // 총 경기 횟수 구하기
        int answer = 0;
        while (n != Math.pow(2, answer)) answer++;
        // a와 b의 크기에 따라 스왑
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        // 이분 탐색을 응용해 계산
        int start = 1, end = n;
        while (start < end) {
            // 중간 값 구하기
            int mid = (start + end) / 2;
            // 두팀이 중간을 기준으로 나눠져 있으면 탈출
            if (a <= mid && b > mid)  {
                break;
            }
            // 두 팀이 나눠져 있지 않으면 범위 변경
            if (b <= mid) {
                end = mid;
            } else {
                start = mid + 1;
            }
            answer--;
        }
        return answer;
    }
}

이 문제를 보고 이분 탐색으로 될거 같이서 로직을 짰습니다. 처음에는 a와 b의 크기로 인한 변경 및 if문에 범위를 잘못 설정해서 틀렸었습니다.

class Solution {
    public int solution(int n, int a, int b) {
        // 총 경기 횟수 구하기
        int answer = 0;
        // 경기하는 라운드 번호를 맞추기 위해 -1
        a--;
        b--;
        while (a != b) {
            a /= 2;
            b /= 2;
            answer++;
        }
        return answer;
    }
}

다른 사람의 풀이를 보니 제거 처럼 위에서 나누면서 가는게 아니라 아래서 올라오는 방법이 있었습니다. 라운드 번호를 맞추기 위해 증감이 필요한데 +로 할경우 상위 경기로 갈때 홀수 기준으로 계산을 해서 계속 더해줘야 합니다. 하지만 -로 맞춰주게 되면 홀수를 짝수로 변경해서 짝수 기준으로 진행하므로 좀더 보기 편해서 해당 방법으로 다시 풀어봤습니다.