Programmers - 예상 대진표 with JAVA (V)

 

 

 

문제

N명의 사람이 대진표를 따라 경기를 진행하는데 A,B는 몇번째 경기에 만날것인지 구하라

 

 

 

로직

만나는 경우는 항상 같다

(1, 2), (3, 4), (5, 6) 과 같이 첫번째 인덱스가 홀수이면서 1차이가 나야한다.

예를 들어, (2, 3)과 같은 경우는 안된다.

또한 위의 경우에 해당하지 않는다면 각각의 인덱스를 2로 나누고 올림처리를 하면 된다.

예를 들어, 인덱스 4라고 가정한다면, 4는 3과 경기를 하고 이기면 2가 되는 방식인 것이다.

 

 

 

코드

class Solution{
    public int solution(int n, int a, int b){
        int answer = 1;
        int x = Math.min(a, b);
        int y = Math.max(a, b);
        while(true){
            if(x%2 == 1 & x+1 == y){
                break;
            }
            answer += 1;
            x = (int)Math.ceil(x/(double)2);
            y = (int)Math.ceil(y/(double)2);
        }
        return answer;
    }
}

 

- 추가적으로 분모는 (double)로 형변환해주자.

 

 

 

다른 아이디어

한 수가 n이하, 한 수가 n 초과임을 통해 구할 수 도 있다. 하지만 이 방법은 중간 중간 알맞은 수를 a, b에서 빼주고 다음 라운드를 진행해야 한다.

 

예를 들어, 16명, 1번과 16번은 결승에서 무조건 만나게 된다. 따라서 16은 2의 4승이므로 4를 반환하면 된다. 하지만 16명, 9번과 16번과 같은 경우 둘 다 8보다 크므로 9와 16을 8을 뺀 후, 다음 라운드를 진행하는 것이다. 코드는 아래와 같다.

 

 

 

코드

class Solution{
    public int solution(int n, int a, int b){
        int max = 0;
        for(int i=1; i<=20; i++){
            if((int)Math.pow(2, i) == n){
                max = i;
                break;
            }
        }
        int x = Math.min(a, b);
        int y = Math.max(a, b);
        while(n != 0){
            n = n/2;
            if(x <= n && y > n){
                return max;
            }
            max -= 1;
            if(x > n && y > n){
                x -= n;
                y -= n;   
            }
        }
        return 1;
    }
}