[프로그래머스 코딩테스트/Python] 예상 대진표 문제풀이

문제 설명

문제 설명
△△ 게임대회가 개최되었습니다. 이 대회는 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 : 2^1 이상 2^20 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

 

 

문제 풀이

이 문제는 풀이 초반에 엄청나게 헷갈리는 문제였다. '해당 대진표를 리스트화해서 탐색하면서 조건에 맞을 때만 다음 라운드로 진출시켜야 하나?'부터 '2차원의 리스트 또는 array를 구현해야 하나?'라는 생각으로 코드를 구현해보려고 했지만 맘처럼 되지 않았다. (코드가 엄청나게 복잡해지는 건 덤...)

 

그러던 도중 문제를 다시 읽어보니 A번과 B번의 숫자 변화가 눈에 띄었다. A와 B는 항상 다음 라운드로 진출하기 때문에, 처음에 배치된 순서 번호로부터 같은 규칙으로 숫자가 변했다.

 

ex)

시작 번호가 4번인 경우: 4(1라운드) -> 2(2라운드) -> 1(3라운드)

시작 번호가 7번인 경우: 7(1라운드) -> 4(2라운드) -> 2(3라운드)

 

이 둘의 공통점은 각 번호에서 '1을 더한 후(홀수로 인해) 2로 나눈 몫'이라는 것이다. 애초에 리스트나 array를 사용할 필요도 없이 이 규칙만 알면 문제를 쉽게 풀 수 있었다.

 

def solution(n,a,b):
    now_round = 0 # a, b가 실질적으로 만날 때까지 계산하므로 0라운드로 시작
    
    while a != b: # a와 b의 2로 나눈 몫이 같다면 같은 라운드에서 상대로 만난 것이므로
        a = (a+1) // 2
        b = (b+1) // 2
        now_round += 1

    return now_round

 

코드가 매우 간단하다. 그 전에 억지로 구현하려 했을 때에는 50~60줄도 넘어갈 뻔했다... ㅎㅎ

코딩테스트 문제를 풀 때 문제를 잘 읽고 그 본질을 파악하는게 확실히 중요하다고 느꼈다. 애초에 파라미터로 받는 N은 코드에 들어가지도 않았으니... 문제에 CS 지식을 덮어 풀기보다는 문제 내 규칙을 찾는 데 더 신경써야 할 것 같다.