[프로그래머스] (Java) 예상대진표 (트리)

 

📑 1. 문제설명

---

💡 2. 풀이 과정

 

문제를 요약하면 토너먼트 게임에서 특정한 번호의 두 참가자가 만날 때 까지 몇 번의 경기를 진행해야 하는지 횟수를 구하는 문제이다. 

 

처음에 참가자들은 1부터 N까지 번호를 받는다.

그리고 다음 라운드에 진출한 참가자들은 다시 1부터 N/2 까지의 번호를 받는다.

 

입출력 예

N=8, A=4, B=7

 

이 경우 8명의 참가자들이 경기를 할 때 4번 선수와 7번 선수가 만날 때까지의 경기 횟수를 아래 그림으로 그려 보았다.

각 라운드에서 4번과 7번은 항상 이겨서 다음 라운드로 진출한다고 가정하고 풀어야 하는 문제이다.

• 4번과 7번은 계속 이겨서 다음 라운드로 진출한다
• 4번은 3번을 이기고, 1 또는 2번을 이겨서 총 2번 이긴다
• 7번은 8번을 이기고, 5 또는 6번을 이겨서 총 2번 이긴다
• 그리고 4번과 7번은 3번째 경기에서 만나게 된다.

여기서 다음 라운드에 진출할 때 번호가 어떻게 되는지 그림으로 표현 해 본 것이다. ▼

 

오른쪽 참가자 번호가 N이고 왼쪽 참가자는 N-1일 때 승자가 다음 라운드에서 받는 번호는 N/2이다.

 

왜냐하면 각 라운드에서는 2명씩 쌍을 이루어 경기 하기 때문에 다음 라운드에서 받을 번호는 이전 라운드를 반으로 나눴다고 생각하면 된다. 

 

이제 이 사실을 이용해서 쉽게 문제를 풀 수 있는데, 문제에서 주어진 두 참가자의 번호가 같을 때까지 이 계산을 반복한다. 두 참가자가 다음 라운드에서 받을 번호가 같다는 것은 두 참가자가 만났다는 뜻이기 때문이다. 그래서 두 참가자 a,b 의번호가 같을 때까지 경기 횟수를 카운트에서 answer 변수에 담아 리턴하면 되는 쉬운 문제이다.

 

---

⭐ 3. 정답코드

class Solution
{
    public int solution(int n, int a, int b)
    {
        int answer = 0;

        // a와 b가 서로 만날 때까지 반복
        for(answer = 0; a != b; answer++) {
            // 다음 라운드에서의 번호 계산 (현재 번호를 2로 나눈 몫)
            a = (a + 1) / 2;
            b = (b + 1) / 2;
        }

        // 두 번호가 같아지는 순간, 두 플레이어가 대결하게 되는 라운드가 결정됨
        return answer;
    }
}