[프로그래머스] 예상 대진표 (JAVA/자바)

[문제 링크]

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

문제 설명

N명의 참가자가 각각 1~N번을 배정받아서 토너먼트 형식의 게임에 참가한다.

1번↔2번, 3번↔4번,... N-1번↔N번 끼리 게임을 진행하고, 다음 라운드에 진출한 참가자들은 다시 1번부터 (N/2)번을 배정받아서 게임을 진행한다.

이 때, 처음 라운드에서 A번을 가진 참가자가 B번 참가자와 만나게 되는 라운드 번호를 구한다.
A번 참가자와 B번 참가자는 서로 만날 때까지 항상 이긴다고 가정한다.

 

 

 

문제 풀이

알고리즘 분류

• 이진탐색

최종 라운드에서 시작해서 아래로 내려가면서 a와 b가 만나는 라운드를 구한다.

N = 2^x 일 때, N명의 참가자가 토너먼트 게임을 진행하면 총 x번의 라운드가 진행된다.

answer의 초기값을 최대 라운드 수인 x로 설정하고, 전체 대진표를 반으로 나눠서 중간값을 mid라고 한다.

(두 구역이 범위는 각각 1~mid, (mid+1)~N)

mid를 기준으로 a와 b가 어느 구역에 속해 있는지 확인한다.

 

a와 b가 서로 다른 구역에 있을 경우, answer 번의 라운드에서 a와 b가 만난다.

a와 b가 서로 같은 구역에 있을 경우, answer번의 라운드보다 더 낮은 라운드에서 만난다.

→ answer을 -1 하고, a와 b가 있는 구역으로 범위를 변경한다.

 

위의 과정을 계속 반복하면서 a와 b가 서로 다른 구역에 있는 경우를 구한다.

전체코드(나의 풀이)

class Solution {
    public int solution(int n, int a, int b) {
        int answer = 0;
        int start = 1, end = n;
        
        //총 라운드 횟수 구하기
        int x = 1;
        for(int i = 1; i <= 20; i++) {
            x *= 2;
            if(x == n) {
                answer = i;
                break;
            }
        }
        
        while(answer > 0) {
            int mid = (start + end) / 2;
            if((a <= mid && b > mid) || (a > mid && b <= mid)) {
                break;
            } else {
                if(a > mid && b > mid) {
                    start = mid + 1;
                } else if(a <= mid && b <= mid) {
                    end = mid;
                }
                answer--;
            }
        }
        return answer;
    }
}

 

 

 

전체코드(다른 풀이)

1라운드부터 시작해서 위로 올라가면서 a와 b가 만나는 라운드르 구한다.

A와 B는 서로 만나기 전까지 항상 이긴다고 가정하기 때문에, 매 라운드마다 번호가 바뀐다.

만약 현재 x번 참가자일 경우, 다음 라운드에서 부여받는 번호는 (x+1)/2 번이다.

ex) 현재 라운드 3번일 경우, 다음 라운드에는 (3+1)/2=2번

      현재 라운드 6번일 경우, 다음 라운드에는 (6+1)/2=3번

 

while문을 돌면서 매 라운드마다 a와 b의 번호를 갱신하면서 두 참가자의 번호가 같아지는 시점을 찾는다.

두 참가자의 번호가 같아지는 시점이 두 참가자가 만나게 되는 라운드이다.

class Solution {
    public int solution(int n, int a, int b) {
        int answer = 1;
        
        while((a + 1) / 2 != (b + 1) / 2) {
            answer++;
            a = (a + 1) / 2;
            b = (b + 1) / 2;
        }
        return answer;
    }
}