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

프로그래머스 '예상 대진표'입니다.

 

문제 링크

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

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

---

● 문제 설명

• 문제 설명△△ 게임대회가 개최되었습니다. 이 대회는 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 입니다.)

---

● 문제 해결 방향

1번과 2번,  3번과 4번, 이렇게 붙는 상대가 정해져 있어

순번을 부여할 때 이 부분에서 오류가 없도록 주의했습니다.

---

● 문제 해결 코드

def solution(n,a,b):
    answer = 1
    
    while (abs(a-b) != 1) or (max(a, b) % 2 != 0):
        
        answer += 1
        
        a = a / 2 if a % 2 == 0 else (a+1) / 2
        b = b / 2 if b % 2 == 0 else (b+1) / 2
        
    return answer

1번과 2번이 붙어 승자가 1번으로

3번과 4번이 붙어 승자가 2번으로

 

a와 b가 각각 빠른 번호인지 느린 번호인지 확인하면서

다음 순번을 부여하는 식을 다르게 적용했습니다.

 

예를 들어, a가 5번인 경우

a는 6번과 붙을 것이고, 결과로 3번을 부여받을 것입니다.

이때 다음 숫자는 짝수 번 / 2 숫자를 부여받으므로

a의 번호가 홀수일 경우 1을 더한 후 나누어 숫자를 부여했습니다.

 

---

● 알게 된 것

알고리즘 적인 면에서 엄청 어려운 문제는 아녔습니다.

하지만 예외 상황을 생각하지 못해서 생각보다 시간이 많이 걸린 문제였습니다.