[프로그래머스] 예상 대진표

문제

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

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

참가자는 각각 1부터 N번을 배정받고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행한다. 각 게임에서 이긴 사람은 다음 라운드에 진출하는데, 다음 라운드에 진출할 참가자는 1번부터 N/2번을 다시 차례대로 배정받습니다. 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받는다. 게임은 최종 한 명이 남을 때까지 진행된다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금하다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 구하라. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정한다.

 

 

풀이

A번 참가자와 B번 참가자가 만날 때까지의 라운드 수를 구하는 문제다.

 

1. 매 라운드마다 A번 참가자와 B번 참가자는 항상 이기기 때문에 항상 번호가 2로 나뉜다. 단, 홀수와 짝수를 모두 고려하면 몫을 올린 값이 다음 라운드의 선수 번호가 된다.

a = math.ceil(a / 2)
b = math.ceil(b / 2)

 

2. 위의 과정을 두 선수의 번호가 같아질 때까지 반복한다.

이긴 횟수가 아니라 라운드 수를 구하는 것이기 때문에 두 선수의 번호가 같아질 때까지 반복할 수 있다.

전체 소스는 다음과 같다.

import math

def solution(n,a,b):
    answer = 0
    while a != b:
        a = math.ceil(a / 2)
        b = math.ceil(b / 2)
        answer += 1
    return answer

 

 

다른 사람 풀이

신기한 풀이가 있어 추가한다.

토너먼트식 경기 진행 방식이므로 두 선수의 번호를 2진수로 취급하는 방법이다.

이로 인해 A번 참가자와 B번 참가자가 인접한 위치로 가는 것이 두 비트가 같을 때는 0을 더하고 두 비트가 다를 때는 1을 더하는 XOR 연산으로 생각할 수 있다.

def solution(n,a,b):
    return ((a-1)^(b-1)).bit_length()

 

 

참고 문서

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