[Programmers] 2017 팁스타운 > 예상 대진표

문제. 2017 팁스타운 > 예상 대진표

---

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

---

입출력 예

N	A	B	answer
8	4	7	3

 

입출력 예 설명

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

 

출처 : 프로그래머스 Level 2 예상 대진표

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

---

나의 풀이

''' 8, 4, 7
1R : 1 2 3 4 5 6 7 8
2R :  1   2   3   4
3R :    1       2
4 -> 2 -> 1 / 7 -> 4 -> 2
서로 붙기 위해서는 b = a
여기서 중요한 점은 a,b를 제외 누가 이기던 상관 없으므로 2를 나눈 몫으로 승자 판별
'''
#import math
def solution(n,a,b):
    answer = 0
    # 진행되는 총 라운드 수
    # total = int(math.log(n) / math.log(2))
    while b != a:
        a =  (a+1)//2
        b = (b+1)//2
        answer += 1
    
    return answer

처음에는 n에 따른 총라운드를 for문을 이용하여 각 라운드별로 리스트를 만들고 최종적으로 a, b가 속한 라운드를 뽑는 식으로 코드를 구현하려고 했습니다. 하지만, 효율성이 떨어져 시간 초과로 실패가 떠서 다시 짜게 되었습니다..ㅠㅠ

 

예시를 직접 그려보며 시나리오를 만들어봤고 a, b를 제외하고 누가 이기던 상관이 없고 a, b가 어떤 라운드에서 만나는 지만 뽑아내면 된다는 것을 알고 수학적으로 생각해봤습니다. a,b가 홀수, 짝수에 관계 없이 1을 더한 상태로 2를 나눈 몫을 추출한 값이 다음 라운드 순서의 값과 일치하기에 결국 마지막에 이를 반복하여 a와 b의 값이 같게 된다면 반복 횟수가 곧 그 라운드의 값이므로 문제가 풀리게 됩니다.

코드가 어려운 문제는 아니었지만, 많이 생각해보고 고민해봐야 답이 나오는 문제라는 것을 알게 되었습니다. 사실 if, else문을 반복해서 사용한다면 쉽게 풀 수 있겠지만 코드의 길이가 엄청나게 길어지기에 그렇게 만든 코드가 효율적이라고는 생각이 들지 않았습니다.