[프로그래머스 Lv2] 예상 대진표 (파이썬)

문제 링크

문제 설명

토너먼트 게임에서 A번 참가자와 B번 참가자가 서로 붙게 되기 전까지 항상 이긴다고 가정할 때, 몇 번째 라운드에서 만나는 지를 반환하는 함수 작성

풀이 코드

def solution(n,a,b):
    # 발생할 수 있는 최대 라운드 수 계산
    max_round = 0
    while 2 ** max_round < n:
        max_round += 1
    
    # 이진 탐색 적용
    a, b = min(a, b), max(a, b)  # 큰 수, 작은 수 구분
    mid = n // 2  # 최초 중간값
    lower = 0  # 최초 최소값
    upper = n  # 최초 최대값
    
    while True:
        # 탈출 조건 // 두 수가 포함된 라운드가 서로 다를 경우
        if a <= mid and b > mid:
            break
        # 작은 수가 중간값보다 클 경우(라운드에서 두 수가 같은 그룹에 있을 경우)
        elif a >= mid:
            lower = mid
            mid = (mid + upper) // 2
            max_round -= 1  # 라운드값 -1
        # 큰 수가 중간값보다 작거나 같을 경우(라운드에서 두 수가 같은 그룹에 있을 경우)
        elif b <= mid:
            upper = mid
            mid = (mid + lower) // 2
            max_round -= 1  # 라운드값 -1
            
    return max_round

코드 설명

0. 대진표를 손으로 그려보다가 반으로 나누어 전후를 살핀다는 점이 이진탐색과 동일하다고 생각하여 이진탐색 기법을 적용하기로 결정
1. 발생할 수 있는 최대 라운드의 수를 계산하기 위하여 while Loop을 활용, 2의 x제곱이 n과 같아지는 시점까지 max_round 변수를 1씩 증가시킴.
2. 이진탐색을 적용하기 위하여 주어진 변수 a와 b의 대소를 비교하여 작은 수를 a에, 큰 수를 b에 재할당하고, 최초 중간값/최소값/최대값을 설정
3. while Loop을 무한 반복하되, 탈출조건으로 두 수가 서로 다른 라운드에 포함되어있을 경우를 설정
4. 이후 라운드에서 두 수가 같은 그룹에 있을 경우를 두 경우로 분할(작은 수가 mid 보다 클 경우, 또는 큰 수가 mid보다 작을 경우)하여 해당 경우에는 max_round를 1씩 뺌

참고 코드

• 스터디 내 다른 사람의 풀이 코드가 훨씬 깔끔하고 쉽게 이해되며 속도도 빨라서, 참고용으로 게시함

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

0. 나는 위에서 내려가며 탐색하는 방법을 취했는데, 이 분은 아래에서 올라갈 때 새로 부여받는 번호의 규칙성을 찾는데 주력하신 듯
1. 마지막에 반환할 변수 round에 초기값 0을 부여
2. a와 b가 서로 다를 경우를 반복하는 while Loop 내에서 시작과 동시에 round를 1 증가시킴
3. 부여받은 각 번호에 1을 더하여 2로 나눈 몫을 다시 각 변수에 저장
4. 각 번호에 1을 더하는 이유
   • 1 ~ 8의 번호가 있을 때, 단순히 2로 나눈 몫은 0 1 1 2 2 3 3 4 이지만 1을 더했을 경우 1 1 2 2 3 3 4 4가 되므로 원하고자 하는 결과값을 얻을 수 있음