프로그래머스 - Level 2. 예상 대진표 / JavaScript (js)

문제설명

문제분석

이 문제는 대진표를 탐색하면서 A와 B가 만날 때까지 걸리는 라운드 수를 구하는 문제입니다. 대진표는 계속 반으로 나누어지므로, 이진 탐색(binary search)을 이용하여 해결할 수 있습니다. A와 B가 만날 때까지 걸리는 라운드 수를 계산할 때, A와 B가 같은 그룹에 속하는지를 판단하면 됩니다. 두 참가자의 번호를 비교해서 둘 중 작은 번호가 짝수이고, 큰 번호가 작은 번호보다 1 크다면 같은 그룹에 속하는 것으로 볼 수 있습니다. 이 경우에는 두 참가자는 다음 라운드에서 서로 만나게 됩니다.

이해하기 쉽게 코드작성하기

function solution(n,a,b) {
    let answer = 1;
    // 같은 그룹(또는 b 가 짝수이고, 남은 참가자가 1이 큰 경우)에 속하지 않으면 반복
    while(!((a % 2 === 0 && b === a - 1) || (b % 2 === 0 && a === b - 1))) {
    	// 반으로 줄여가며 탐색(이진탐색)
        a = Math.ceil(a / 2);
        b = Math.ceil(b / 2);
        answer++;
    }
    
    return answer;
}

코드 설명

위 코드를 변경한다면, while문 안의 내용을 추상화하거나 a, b를 정렬한 다음 적용하는 방법이 있습니다.

function solution(n,a,b) {
    let answer = 1;
    while(isDifferentGroup(a, b)) {
        a = Math.ceil(a / 2);
        b = Math.ceil(b / 2);
        answer++;
    }
    
    return answer;
}

// while문 추상화
function isDifferentGroup(a, b) {
    return !((a % 2 === 0 && b === a - 1) || (b % 2 === 0 && a === b - 1))
}

만약 a, b를 정렬한다면, 다음과 같은 접근도 가능합니다. 같은 라운드에서 만난다는 말은, a와 b가 같은 값이 된다는 경우입니다.

function solution(n,a,b) {
    let answer = 0;
    [a, b] = [Math.min(a, b), Math.max(a, b)];
    
    while(a !== b) {
        a = Math.ceil(a / 2);
        b = Math.ceil(b / 2);
        answer++;
    }
    
    return answer;
}