프로그래머스 Lv.2) 예상 대진표

예상 대진표

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

풀이

이 문제를 2일 전인가 쯤 같이 취준하고있는 형한테 문제를 받았었다. 풀이는 비트 연산을 통해서 경기 수를 구하는 것이었다.

하지만, 내가 비트연산으로 문제를 풀기에는 아직 무리라는 생각이 들어서 나만의 방식으로 풀기로 했다.

궁금하신 분은 여기에서 확인하시면 좋을 것 같습니다. : )

 

처음 풀었을 때는 1번과 25번이 시관초과가 떴었다. 그래서 바로 매치를 할 수 있는 경우를 추가시켜주었다.

if(left%2 ==1 && right -left ==1) {
return 1;
}

이 부분을 추가해주자 1번이 통과되었다.

하지만 25번이 계속 시간초과가 뜨길래 뭔가하다가, 혹시 a, b가 오름차순으로 주어지지 않았을 수 있다는 생각에 left, right를 만들어 오름차순으로 검사하게 두었다. 그러자 통과가 되었다.

 

로직은

1. 2의 제곱을 각 배열에 저장한다.

2. 각 숫자에 해당하는 지수를 구한다.

 2-1. 두 지수의 차이가 있다면, 해당 지수만큼 경기를 치뤄야하는 규칙 때문에, 더 큰 지수값을 리턴하게 했다.

3. 두 지수가 같다면, 그보다 1 작은 지수의 수만큼 빼주고 지수가 달라질 때 까지 반복한다.

4. 2-1을 적용하고 return한다.

 

3의 이유는 경기 규칙을 찾아보면 이해할 수 있습니다.

n이 1인 경우 선수는 2명, 경기는 총 1 번 치르게 됩니다.

n이 2인 경우 선수는 4명, 경기는 총 3 번, 라운드는 2라운드까지 진행합니다.

n이 3인 경우 선수는 8명, 경기는 총 15번, 라운드는 3라운드까지 진행합니다.

따라서 총 경기는 2^n -1번, 라운드는 n까지 경기를 진행하는데, 지수가 늘어날 때마다 하나의 구역이 되어, 2^(n-1)+1 ~ 2^n과 1 ~ 2^(n-1)로 각각 준결승까지(이하 리그) 경기를 치릅니다.

지수를 하나씩 줄여주면서 리그에서 총 몇 경기를 치뤄야하는 범위를 좁혀나가는 것이라고 생각하면 될 것 같습니다.

 

코드

class Solution
{
    public int solution(int n, int a, int b) {
        int result =0;
        int left = Math.min(a,b);   //25번이 안돼서 추가
        int right = Math.max(a,b);
        
        int[] exponentArr = getExponentArr();
        int player1 = getExponent(left,exponentArr);
        int player2 = getExponent(right,exponentArr);
        if(left%2 ==1 && right-left ==1) {  // 1번, 25번
            return 1;
        }
        while(player1 == player2) {
            left-= exponentArr[player1-1];
            right-= exponentArr[player2-1];
            player1 = getExponent(left,exponentArr);
            player2 = getExponent(right,exponentArr);
        } 
        result = Math.max(player1, player2);
        return result;
    }
    
    private int[] getExponentArr() {
        int[] result = new int[21];
        for(int i=1; i<=20; i++) {
            result[i] = (int)Math.pow(2,i);
        }
        return result;
    }
    
    private int getExponent(int num, int[] arr) {
        int result =1;
        for(int i=1; i<=20; i++) {
            if(num <=arr[i]) {
                result = i;
                break;
            }
        }
        return result;
    }
}