프로그래머스 Lv2 예상 대진표 Java

문제설명

https://programmers.co.kr/learn/courses/30/lessons/12985

구현방법

• 처음 n명을 좌, 우 각각 절반으로 나눈 뒤 A, B가 서로 다른쪽에 있는지 판단함.

• 만약 맨 처음 서로 다른쪽에 있다면 두 선수는 모든 매치의 마지막 단계에서 대결하게 된다.

• 최종 대결 단계 수는 log2의 n이다. 예를들어 n이 8인 경우 최종 대결 단계수는 3이다.

• 이 과정을 반복해서 서로 다른쪽에 있을 때가 두 선수가 맞붙는 단계이다.

• 다만 두 선수가 모두 우측에 있는 경우 n을 2로 나누어 반복문을 돌리기가 어렵기 때문에 우측에 있는 경우 두 선수를 모두 좌측으로 옮긴다.

코드

import java.util.*;
class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = (int)logB(n,2);

        while(true){
            //두 선수 모드 다른쪽에 있는 경우 break
            if(a<=n/2&&b>n/2||b<=n/2&&a>n/2){
                break;
            }
            else{
                //두 선수 모두 우측에 있는 경우 좌측으로 이동시킴
                if(a>n/2){
                  a -= n/2;
                  b -= n/2;
                }
                n /= 2;
                answer--;
            }
        }
        return answer;
    }
    double logB(double x, double base) 
    { 
        return Math.log(x)/Math.log(base); 
    }

}