Level 2 예상 대진표 Python3

programmers.co.kr/learn/courses/30/lessons/12985

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

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

from math import ceil

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

 

---

풀이 과정

풀이 시간 14분

Ceil 함수의 활용

 나는 이 문제를 해결하기 위해 math 모듈의 ceil함수를 활용했다. (ceil함수가 포함된 math 모듈에 대한 참고는 아래를 살펴보면 된다.)

이 문제에서 주의해야 할 점은 (1, 2), (3, 4), (5, 6) · · · 으로 짝지어진 참가자끼리 게임이 진행된다는 점이다. 따라서 1번부터 차례대로 두 명씩 짝짓기 때문에 2번과 3번, 또는 4번과 5번 참가자끼리 묶이지 않는다.

이에 따라, 나는 1번과 2번 참가자가 서로 붙는다는 것을 ceil(1/2) = 1, ceil(2/2) = 1이라는 점에서 확인 했다.

참가자 번호를 각각 2로 나누어 올림한 결과가 같지 않다는 것은 서로 다른 참가자와 경기를 했다는 의미이다. 문제에서 주어지는 a번과 b번의 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정한다고 되어 있기에, 계속해서 2를 나누고 올림한 값을 비교 해 나갔다.

 여기서, 2로 나눈다는 것은 다음 라운드라는 것을 의미한다.

 

 이를 코드로 작성한 것이 아래과 같다.

from math import ceil

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

ceil(a/2) == ceil(b/2)일 때까지 while문이 반복되어 a번과 b번 참가자가 다음 라운드에 진출해 새 번호를 부여받는다. 이때마다 몇 번째 라운드인지 나타내는 answer가 카운팅되어 ceil(a/2) == ceil(b/2)일 때, answer값이 반환된다.

 

 

---

다른 사람의 풀이

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

비트 연산자 ^ 활용

 먼저, ^는 비트를 XOR 연산을 하는 연산자이다. a와 b를 각각 2비트로 표현 했을 때, 각 자리의 비트를 비교해서 같으면 0, 다르면 1이 더해진다.

예를 들어, a = 5 = 101(2)이고 b = 6 = 110(2)라면, a^b = 011(2) = 11(2)이므로 10진수로 표현하면 3이다. 

비트 연산을 하기 전에 1을 각각 빼준 이유는 아래 표를 참고하면 이해 할 수 있다.

10진수로 표현한 a, b	2비트로 표현한 a, b	a^b 결과	(a^b).bit_length() 결과
a = 0, b = 1	a = 0(2), b = 1(2)	1(2) = 1	1
a = 1, b = 2	a = 1(2), b = 10(2)	11(2) = 3	2
a = 2, b = 3	a = 10(2), b = 11(2)	1(2) = 1	1
a = 3, b = 4	a = 11(2), b = 100(2)	11(2) = 3	2
a = 4, b = 5	a = 100(2), b = 101(2)	1(2) = 1	1
a = 5, b = 6	a = 101(2), b = 110(2)	11(2) = 3	2
a = 3, b = 6	a = 11(2), b = 110(2)	101(2) = 5	3
a = 4, b = 7	a = 100(2), b = 111(2)	11(2) = 3	2

첫 번째 행과 2번째 행의 경우 (a^b).bit_length() 결과를 살펴보면 각각 1과 2가 나왔다. 문제를 보면 1부터 N번을 차례대로 배정 받기 때문에 a = 1, b = 2인 경우 1 라운드에서 서로 붙게 된다. 따라서 각각 -1을 한 0과 1인 첫번째 행인 경우가 (a^b).bit_length() = 1로 결과가 맞게 나온 것을 확인 할 수 있다. 이런식으로 그 다음 행들도 살펴보면 a와 b에 각각 -1을 해준 이유를 이해 할 수 있다.

 

 그렇다면, 문제의 예시로 나온 a = 4, b = 7인 경우를 적용해보자. 위의 표의 마지막 두 행을 살펴보면 된다.

a = 3, b = 6인 경우(a와 b에 각각 -1을 해준 경우), a^b = 101(2) 되어 (a^b).bit_length()의 결과 3이 출력된다.

a = 4, b = 7인 경우(a와 b에 각각 -1을 해주지 않은 경우), a^b = 11(2) 되어 (a^b).bit_length()의 결과 2가 출력된다.

실제로 직접 대진표를 작성 해 보면, 1 라운드에 a번 참가자는 3번 참가자와, b번 참가자는 8번 참가자와 각각 붙어 a와 b가 승리한다. 2 라운드에서 다시 a번 참가자는 2번을 부여 받아 1번 참가자와, b번 참가자는 4번을 부여 받아 3번 참가자와 각각 경기하였고 a와 b가 승리한다. 3 라운드에서 다시 a번 참가자는 1번을 부여 받고, b번 참가자는 2번을 부여 받아 서로 붙게 되어 답은 3이 된다.

따라서, ((a-1)^(b-1)).bit_length() = 3이 성립된다.

 

 

---

참고

• 2021/01/14 - [Python/라이브러리] - math

math