예상 대진표

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

코딩테스트 연습 - 예상 대진표

(프로그래머스 > 코딩테스트 연습 > 2017 팁스타운 > 예상 대진표(level2))

 

---

 

<문제>

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. 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번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

• N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

 

---

 

<내가 작성한 코드>

def solution(N,A,B):
    rangeA = 0
    rangeB = 0

    for i in range(1,21):
        if 2**(i-1)<A and 2**i>=A:
            rangeA = i;
        if 2**(i-1)<B and 2**i>=B:
            rangeB = i;
        if rangeA!=0 and rangeB!=0:
            break

    if rangeA!=rangeB:
        return max(rangeA, rangeB)
    else:
        A -= 2**(rangeA-1)
        B -= 2**(rangeB-1)
        return solution(N,A,B)

-> 2의 n승 차이가 날때마다 경기의 횟수는 늘어난다는 법칙을 이용

ex) A = 9, B = 31이면,  8<A<=16 이고 16<B<=32라고 바꿔 말할 수 있다.

    즉 2^3<A<=2^4 이고, 2^4<B<=2^5 인데 직접 그려보면 두 사람은 5번째 경기에서 만나게 된다

    => 두 사람이 각기 다른 2의 n승과 m승에 있을 경우, n과 m 중 큰 숫자번째 경기에서 둘이 만나게 된다.

    => 둘이 범위가 같을 경우, 둘의 범위가 달라질 때까지 A,B를 동일하게 변형시켜 반복한다(재귀)

 

2의 몇승인지에 따라 나눠지는 경기 수

 

 

 

 

<다른 사람의 코드를 참고한 코드 1>

def solution(N,A,B):
    return ((A-1)^(B-1)).bit_length()

->  A와 B를 2진수로 변환한뒤 XOR을 취한다(A와 B의 거리가 가까우면 상위 비트는 차이가 나지 않음.) A와 B는 1부터 주어지지만 우리는 0부터 고려해야함으로, A와 B에서 1씩 빼줌

ex) A = 9, B = 31이면, 

    bin(A-1) = 1000     bin(B-1) = 11110   => (A-1)^(B-1) = 10110 =>  ((A-1)^(B-1)).bit_length() = 5

 

  +) bit_length() : 주어진 수를 2진수로 변환한뒤 그 길이를 반환하는 함수

def bit_length(self):
    s = bin(self)       # binary representation:  bin(-37) --> '-0b100101'
    s = s.lstrip('-0b') # remove leading zeros and minus sign
    return len(s)       # len('100101') --> 6

 

 

 

<다른 사람의 코드를 참고한 코드 2>

def solution(N,A,B):
    answer = 0
    while A!=B:
        answer+=1
        A,B = (A+1)//2, (B+1)//2
    return answer

-> A, B 각각의 경우로 고려. round 올라갈때마다 남는 인원수를 체크하는데 A와 B에 남는 인원이 동일할때까지 반복.

ex) A = 9, B = 31이면,

A	B	answer
9	31	0
5	16	1
3	8	2
2	4	3
1	2	4
1	1	5

 

---