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

문제

세모세모 게임대회가 개최됐다. 이 대회에는 N명이 참가하고 토너먼트 형식으로 진행한다.

N명의 참가자는 각각 1부터 N을 차례대로 배정받는다.

게임은 1번↔2번, 3번↔4번, ... , n-1번↔n번 참가자끼리 진행한다.

 

게임 참가자 수 n, 참가자 번호 a, 경쟁자 번호 b가 매개변수로 주어질 때 처음 라운드에서 A번을 가진 참가자는 경쟁자인 B번 참가자를 몇 번째 라운드에서 만나는지 반환하는 함수를 만들어야 한다.

 

 

제한사항  

1. N: \(2^1\)이상 \(2^{20}\) 이하인 자연수 (따라서 부전승 없음)

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

 

 

코드

from math import log2

def solution(n, a, b):
    A = a if a < b else b
    B = b if a < b else a

    group_dict = {
        'A': '',
        'B': ''
    }

    group_dict['A'] = 'left' if A <= n/2 else 'right'
    group_dict['B'] = 'left' if B <= n/2 else 'right'
    
    if group_dict['A'] != group_dict['B']:
        return int(log2(n))
    elif group_dict['A'] == 'left' and group_dict['B'] == 'left':
        return solution(int(n/2), A, B)
    else:
        return solution(int(n/2), A-(n/2), B-(n/2))

 

 

설명

그림 1

글로하면 설명이 지저분해질것 같아 그림을 직접 그려봤다.

그림 1처럼 n/2 지점을 기준으로 a와 b가 다른 방향에 있다면 이 둘은 반드시 \(log_{2}n\)번째 라운드에서 만나게 된다.

n/2을 기준으로 왼쪽을 그룹1 오른쪽을 그룹2라고 했을 때, a는 그룹1 경기를 모두 끝마쳐야 b를 만날 수 있고 b또한 그룹2 경기를 모두 끝마쳐야 a를 만날 수 있기 때문이다.

 

 

그림 2

만약에 둘 다 같은 방향에 있다면 (n/2)/2를 기준으로 다시 반복한다.

a와 b가 반대 방향에 있게 될 때 까지 n/2를 2로 나누면서 반복해준다.

 

 

그림 3

둘 다 같은 방향일 때, 왼쪽과 오른쪽을 구분해줘야하는데

그림 3과 같은 상황에서 a와 b가 모두 오른쪽으로 같은 방향일 때는 (n/2)/2를 기준으로 하면 무한반복이 생기기 때문이다.

이 때는 a와 b에 (n/2)를 빼주어 왼쪽에서 계산이 가능하도록 해준다.

이 것이 가능한 이유는 토너먼트 형식이 좌우대칭이기 때문이다(1과 5, 2와 6, 3과 7 등등).

 

위 그림들을 코드로 구현해본다.

 

A = a if a < b else b
B = b if a < b else a

문제에서 a와 b가 항상 오름차순으로 정렬되어 있다고 언급하지 않았기 때문에

계산 전에 A가 항상 B보다 작도록 설정해준다.

 

group_dict = {
	'A': '',
	'B': ''
}

A와 B가 각각 n/2를 기준으로 어느 쪽에 속해 있는지를 저장해둘 딕셔너리이다.

 

group_dict['A'] = 'left' if A <= n/2 else 'right'
group_dict['B'] = 'left' if B <= n/2 else 'right'

A와 B를 n/2와 비교하여 작다면 딕셔너리에 left로, 그렇지 않다면 right로 기록한다.

 

if group_dict['A'] != group_dict['B']:
	return int(log2(n))

A와 B가 서로 반대 방향이라면 n에 \(log_{2}\)를 취한 값을 반환한다.

 

elif group_dict['A'] == 'left' and group_dict['B'] == 'left':
	return solution(int(n/2), A, B)

A와 B가 left로 같은 방향이라면 n/2의 값을 매개변수 n으로 넣어 재귀한다.

 

else:
	return solution(int(n/2), A-(n/2), B-(n/2))

A와 B가 right로 같은 방향이라면 매개변수 n, a, b에 각각 n/2, A-(n/2), B-(n/2)를 넣어 재귀한다.