[12985] 예상 대진표

✔ 예상 대진표

[프로그래머스 12985]

문제 분석하기

1, 2번은 1번째 라운드에서 게임을 진행하고 이때 이긴 사람은 다음 라운드에서 1번

3, 4번은 1번째 라운드에서 게임을 진행하고 이때 이긴 사람은 다음 라운드에서 2번

n - 1, n번은 1번째 라운드에서 게임을 진행하고 이때 이긴 사람은 다음 라운드에서 (n + 1) / 2번

이를 차례대로 반복했을 때, A번 참가자와 B번 참가자가 몇 번째 라운드에서 만나는지 찾도록 함

 

예) 8명 참가, 4번 참가자와 7번 참가자가 만나는 라운드

라운드	A번 참가자의 번호	B번 참가자의 번호
1	현재 4번 → 다음 라운드에서 2번	현재 7 → 다음 라운드에서 4번
2	현재 2 → 다음 라운드에서 1번	현재 4 → 다음 라운드에서 2번
3	현재 1 → 다음 라운드에서 1번	현재 2 → 다음 라운드에서 1번
4 라운드에서 둘이 모두 1번이 되므로 둘이 게임을 하여 승자가 1번이 되는 것

손으로 풀어보기

1. 두 번호를 다음 라운드의 번호로 변경
   • A와 B의 번호가 같다면 두 참가자가 게임을 하여 둘 중 한 명이 다음 라운드 승자가 되므로 그 라운드에서 서로 붙게 됨
   • 그러므로 두 참가자를 (현재 번호 + 1) / 2 값으로 갱신하고 같은지 확인
2. 라운드 반환

슈도코드 작성하기

n(게임 참가자 수)
a, b(참가자 번호와 경쟁자 번호)
answer(A번 참가자가 B 참가자와 만나는 라운드)
while(a와 b가 같지 않을 동안) {
    answer 증가
    a를 다음 라운드 번호인 (a + 1) / 2로 갱신
    b를 다음 라운드 번호인 (b + 1) / 2로 갱신
}
answer 반환

코드 구현하기

/**
 * 12985) 예상_대진표
 */
public class L027_12985 {
    // n(게임 참가자 수)
    // a, b(참가자 번호와 경쟁자 번호)
    public int solution(int n, int a, int b) {
        // answer(A번 참가자가 B 참가자와 만나는 라운드)
        int answer = 0;
        // a와 b가 같지 않을 동안
        while (a != b) {
            // answer 증가
            answer++;
            // a를 다음 라운드 번호인 (a + 1) / 2로 갱신
            a = (a + 1) / 2;
            // b를 다음 라운드 번호인 (b + 1) / 2로 갱신
            b = (b + 1) / 2;
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L027_12985 solution = new L027_12985();

        int n = 8;
        int a = 4;
        int b = 7;

        int result = solution.solution(n, a, b);

        System.out.println(result);
    }
}