[cote] 예상 대진표

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

프로그래머스

 

문제 설명

 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

 이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

 

제한사항

• N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

 

풀이

문제는 간단하다. n명의 사람의 토너먼트를 붙으면 a번과 b번은 몇번째 경기에 만날 수 있는지를 묻는 것.

 

    public int solution(int n, int a, int b) {
        int answer = (int) (Math.log(n) / Math.log(2));

        int[] arr = new int[]{Math.min(a, b), Math.max(a, b)};			---[1]

        int p1 = 0;
        int p2 = n/2;
        int p3 = n;

        while (true) {
            if (((p1 < arr[0] && arr[0] <= p2) && (p2 < arr[1] && arr[1] <= p3))) {
                break;									---[2]
            } else if (((p1 < arr[0] && arr[0] <= p2))) {				---[3]
                p3 = p2;
            } else if (((p2 < arr[0] && arr[0] <= p3))) {
                p1 = p2;
            }
            p2 = (p1 + p3) / 2;
            answer--;
        }
        return answer;
    }

 나는 이렇게 풀었다.

 

 토너먼트는 구조가 b tree와 같으므로 묻고자 하는 a, b가 갈라지는 지점까지 타고들어가는 방식으로 생각해서 풀었다.

 

 [1]번은 a, b가 어떤 값이 큰지 알려주지 않아 그냥 배열로 받았다. 다른 사람의 코드에서는 크기에 따라 순서를 변경해주는 코드도 있었다.

 

 [2]번에서 a, b가 왼쪽, 오른쪽으로 갈라지면 반복문을 중단한다.

 

 [3]은 [2]번에서 왼쪽 혹은 오른쪽에 둘 다 위치함을 알았으니 a,b의 위치에 따라 p1,2,3을 변경하여 다음 반복문을 진행할 수 있도록 초기화를 하는 단계이다.

 

다른 풀이

    public int solution2 (int n, int a, int b) {
        int round = 0;
        while(a != b) {
            a = a/2 + a%2;
            b = b/2 + b%2;
            round++;
        }
        return round;
    }

a, b가 같아지면 대전을 치룬다는 개념으로 푼 것 같다. 2진 트리이기 때문에 위치는 2로 나눈 값이 나머지가 있으면 오른쪽 없으면 왼쪽으로 간다.

매 회를 치룰 때마다 번호를 다시 지급받게 된다고 생각하면 쉽다.

대진표	1회 이후

 이진 트리의 특성을 놓친 것 같아서 정리해두면 좋을 것 같아 글을 남긴다.

 

다른 풀이 2

이외에도 XOR 게이트 사용한 방식도 있었다.

    public int solution3(int n, int a, int b) {
        return Integer.toBinaryString((a-1)^(b-1)).length();
    }

 너무 간단한데 처음에 문제를 보고 머리로는 이렇게 풀면 되겠다 생각했지만 코드로 풀이를 할 수 없었다.

 

 ^는 XOR 비트 연산자로 이진 수 a와 b의 대해서 a,b가 같으면 0 다르면 1을 반환하는 연산자이다.

 

예를 들어 a=3 b =7일 때는 코드에 따라 2 ^ 6을 연산하게 되고 이를 2진으로 바꾸면.

 

010 ^ 110이다. 이는 100이 되므로 길이는 3이다. 즉, 3번째 라운드에서 만나게 된다.

 

 내가 문제를 보고 풀려고 했을 때 같이 존재하는 최대의 이진 트리 꼭대기 노드가 몇번째 라운드인지를 알면 된다고 생각했었는데 이를 코드로 작성하기가 어려웠고 꼭대기 노드부터 내려가는 코드를 짰다.

 

하지만 ^ 연산자를 활용하면 몇번째 노드에서 만나는지 바로 확인할 수 있었다.

 

 0001001

 0000110

 

위 두명은 4번째 라운드에 만난다. 2진 총 길이는 노드가 나눠지는 횟수이며 총 라운드의 숫자를 말한다.

 

이진과 트리의 특성을 이해한다면 이 문제를 쉽게 풀 수 있다.