예상 대진표

문제정의

---

부전승이 없고 n명의 선수가 토너먼트를 진행할 때, 두 선수가 만날 라운드 수를 반환하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

package level2;

public class ExpectTournament {

    //프로그래머스 문제풀이 Level2 예상 대진표
    public static void main(String[] args) {
        int n = 8, a = 4, b = 7;
        boolean flag = false;
        int total_round = Integer.toBinaryString(n).length()-1;
        int l = Math.min(a,b);
        int r = Math.max(a,b);
        int answer = total_round;
        int size = 2;
        for(int i = 1; i <= total_round; i++)
        {
            
            for(int j = 1; j <= n; j+=size)
            {
                if(j <= l && r <= j+(size-1))
                {
                    answer = i;
                    flag = true;
                    break;
                }
            }
            if(flag)
                break;
            size *= 2;
        }
        System.out.println(answer);
    }
}

원래 재귀로 풀었었는데, 런타임 에러가 자꾸 떠서 결국 방법을 바꾸었다. 비주얼 스튜디오 코드에서는 동작했던 걸 보아하니 채점 사이트에서 막은 건가 싶었다. 어쨌든 새로 한 두번째 방법은 2명씩 4명씩 8명씩.. 이런식으로 계속 묶어나가며 a,b가 동시에 속한 경우를 발견하면 그 라운드를 i에 받고 반복문을 마친다.

코드를 좀 더 자세히 설명하자면, total_round는 이진법으로 바꾼 문자열에서 -1하면 된다. 그리고 l은 두 선수 중 숫자가 작은 쪽, r은 숫자가 큰 쪽이다. 1라운드부터 최종라운드까지 선수들을 묶어가면서 범위에 두 선수가 속해있는지 확인한다. 이때 초기 size는 선수가 2명씩 묶이므로 2로하고 라운드를 진행할 수록 팀 당 선수는 2배씩 늘어나므로 size도 2를 곱해준다.

최종 시간복잡도는 공비가 \(1\)인 등비수열의 합이므로, 2진법을 계산하는 과정이 있기 때문에 \(O(n*{1}^n)\)이다.

테스트

비트 연산을 통해서 문제를 푼 것을 보고 감탄을 느꼈다. 2로 나누거나 곱하는 연산은 비트 연산을 통해 풀어볼 수 없는지 공부해 봐야겠다.