규도자 개발 블로그

[프로그래머스/Level2/파이썬3(python3)] 예상 대진표 본문

알고리즘/풀이

[프로그래머스/Level2/파이썬3(python3)] 예상 대진표

규도자 (gyudoza) 2021. 7. 17. 17:31
반응형

[프로그래머스/Level2/파이썬3(python3)] 예상 대진표

문제

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

입출력 예

NABanswer
8473

입출력 예에 대한 설명

입출력 예 #1 첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

풀이

from math import ceil


def solution(n, a, b):
    answer = 1
    if b < a:
        a, b = b, a
    while n > 2:
        if a - b == -1 and a % 2 != 0:
            break
        a = ceil(a/2)
        b = ceil(b/2)
        n = n // 2
        answer += 1
    return answer

설명

참가번호를 entry라고 정의했을 때 각 entry는 다음 라운드에 진행될 때마다 ceil(entry/2)라는 entry를 새로 갖는다. 라운드가 진행되면서 a와 b의 entry를 계속 추적하는데 이들이 같은 라운드에서 붙게 되거나 혹은 결승까지 진행됐을 때 반복문을 종료시키는 식으로 코드를 작성하였다. a가 b보다 빠른 엔트리에 작성돼있어야만 둘이 같은 라운드에서 붙는지 검사하는 조건문(if어쩌구)에 충족되므로 맨 처음의 조건문을 통해 a가 무조건 b의 entry보다 작은 수를 가질 수 있게 조절하였다. 만약에 실세계에 이 코드를 대입한다면 a와 b의 entry가 바뀔 가능성이 있으니 진짜 그냥 문제의 용도(몇 번 라운드에 붙는지)로만 쓸 수 있는 코드라고 할 수 있다.

반응형
0 Comments
댓글쓰기 폼