[프로그래머스] Lv.02 연습문제 예상 대진표 (JavaScript)

문제설명

△△ 게임대회가 개최되었다고 한다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행된다.

N명의 참가자가 1번부터 N번까지 차례대로 배정 받고, 1번<->2번, 3번<->4번, ... , N-1번<->N번의 참가자가 대진을 하는 방식으로 진행된다. 각 게임에서 이긴 사람은 다음 라운드에 진출하고 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받는다. 1,2번의 대진에서 이긴 사람이 다음 차례 1번을 부여받는 방식이다. 게임은 최종 한 명이 남을 때까지 진행된다.

게임을 진행하는 동안 처음 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 알고 싶다고 할 때, 몇 번째에 만나는지 구해 리턴을 하면 되는 문제이다.

※제한사항

 -A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다. 

 - N : 2^1 이상 2^20 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않는다.) 

 - A,B : N 이하인 자연수 (단, A != B 이다.)

풀이

제한사항을 살펴보면 "A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다." 라는 부분이 있다. 그리고 해당 문제는 1번부터 N번까지 있을 때 토너먼트 형식으로 진행되고 다음 라운드에서 N/2의 순번이 새로 부여된다고 나와있다.

그러면 A번과 B번을 나누기 2를 해주면 A와 B가 같은 번호가 되는 타이밍은 A와 B가 대진에서 만나 붙은 다음 번호가 된다는 말과 같다. 그렇기 때문에 A와B의 번호가 같아질때까지 Math.ceil(a/2), Math.ceil(b/2) 연산을 해주고, 라운드 수를 체크해주면 A와 B가 언제 만나는지 구할 수 있다.

아래는 풀이에 사용한 코드이다.

function solution(n,a,b)
{
    var answer = 0; // 라운드를 체크할 변수
    // a와 b가 같으면 만난 이후 이므로 반복문 정지
    while(a != b) {
        a = Math.ceil(a/2) // 항상 앞 번호로 부여 받으므로 내림차수로 나눠준다
        b = Math.ceil(b/2) // 항상 앞 번호로 부여 받으므로 내림차수로 나눠준다
        answer++
    }
    return answer;
}