예상 대진표 (level2)

링크

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

문제

토너먼트를 진행하는데 토너먼트의 승자는 다시 1부터 n/2까지 새로운 번호를 할당 받는다. 예를 들어 5, 6번 선수들의 승자는 3번을 배정 받는다. 총 인원 n, 라이벌 관계의 두 사람의 번호가 a, b 일 때, 두 사람은 몇 번째 경기에서 만나게 될 것인가?

예제로 이해

총 인원 8명이고, a = 4, b = 7일 때, 첫 경기가 진행되면 각각의 선수는 2, 4번을 재 할당 받는다. 다음 두 번째 경기가 끝나면 각각 1번, 2번을 할당 받는다. 두 사람은 다음 경기에서 만나게 되므로 3을 반환해준다.

코드

function solution(n,a,b) {
    let count = 1
    let min = Math.min(a, b)
    let max = Math.max(a, b)
    
    for(let i = 0; i < Math.log2(n); i++, count++) {
        if(min % 2 === 1 && max - min === 1) {
            return count
        } else {
            min = Math.ceil(min / 2)
            max = Math.ceil(max / 2)
        }
    }
}

코드 풀이

가장 먼저 두 선수 중 앞번호와 뒷번호를 구분지어준다. 연속되는 번호를 가질 때 두 선수가 만나게 되지만 만약 4, 5일 경우 연속되는 번호이지만 다음 경기에서나 만날 수 있기 때문에 이런 경우를 제외하기 위해서 앞번호와 뒷번호를 구분지어 앞번호가 홀수, 뒷번호가 짝수이고, 연속되는 경우에 만나는 것으로 한다.

반복문을 진행하는데 반복문은 토너먼트 경기 특성 상 경기는 log2(n)만큼만 진행되기 때문에 해당 값을 반복문의 조건문으로 활용한다.

두 선수가 이번 경기에서 만나지 않을 경우에는 두 선수의 번호를 2로 나누어주고 올림을 진행하여 새로운 번호로 할당해준다.