[문제 바로가기] 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
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.
💡 문제 풀이
부전승이 없는 예상대진표가 되려면 N(참가자 수)값은 2n(1 <= n <= 20)이 되어야 한다.
이 때, a와 b가 대진표상에서 가장 늦게 만나는 경우도 n이 된다.
따라서, 이진탐색을 이용하여서 반씩 나누면서 a와 b가 몇 번째 대진에서 만나는지 찾고자 했다.
※반씩 나누는 과정에서 중간값을 기준으로 a와 b가 양쪽에 위치한다면 n(가장 늦게 만나는 경우) - 반으로 나눈 횟수 값을 return 하면 된다.
- left : 이진탐색시 왼쪽 끝 값
- right : 이진탐색시 오른쪽 끝 값
- center : 이진탐색시 중간 값
- cnt : 예상 대진표에서 a와 b가 가장 늦게 만나는 경우의 횟수
step 1)
a와 b에 각각 둘 중 작은값, 큰값으로 입력 (for 이진탐색)
step 2)
양쪽 끝 값(left=1, right=n)을 설정하고 중간값(center) 도출
step 3)
if 중간값을 기준으로 a와 b가 나뉘어져 있으면
cnt값에서 a와 b가 대진한다는 뜻이다.
a조건의 부등식에서 '='를 포함하는 이유는 중간값(center)이 왼쪽 끝 값에 위치하기 때문
ex) 1 2 3 4 | n = 4, a = 1, b = 3의 경우
cnt = 2 (22 = 4)
center = 2가 된다.
center(2)를 기준으로 a는 왼쪽 b는 오른쪽에 위치하고 있으므로 cnt(2번째)횟수에 a와 b는 대진하게 된다.
만약 a가 2이고 b가 4여도 중간값을 기준으로 횟수를 구하기 때문에 문제가 없다.
elif 중간값이 a보다 작으면 우측 방면에 대해 이진탐색
- left, center값 최신화
- 이진탐색을 하였으므로 cnt값 -1
elif 중간값이 b보다 크면 좌측 방면에 대해 이진탐색
- right, center값 최신화
- 이진탐색을 하였으므로 cnt값 -1
step 4)
while문을 마치면 cnt값을 return한다.
코드는 아래와 같다.
풀이 1
def solution(n,a,b):
a, b = min(a,b), max(a,b)
answer = 0
cnt = 0
for i in range(1, 21):
if 2**i == n:
cnt = i
left = 1
right = n
center = (left + right) // 2
while True:
if center >= a and center < b:
break
elif a >= center:
left = center
center = (right + center) // 2
cnt -= 1
elif center >= b:
right = center
center = (left + center) // 2
cnt -= 1
return cnt아주 간단하게 대진표의 번호에 접근하는 방법도 있다.
문제 설명처럼 대진표에 승리한 사람은 순서대로 1부터 n/2까지의 번호를 새롭게 배정받는다.
즉, 두 개의 값 중 하나는 반드시 올라오기 때문에 2로 계속 나누면서 반복하다보면 두 값은 결국 대진하는 상황에 마주하게 된다.
코드는 아래와 같다.
풀이 2
def solution(n,a,b):
answer = 0
while a != b:
a = (a+1) // 2
b = (b+1) // 2
answer += 1
return answer단, a+1과 b+1을 해주는 이유는 a와 b가 각각 1, 2일 경우를 생각해보면 된다.
각각 2씩 나누게 되면
1, 2 → 0, 1 이 된다.
하지만 +1을 해주게 되면
(1+1), (2+1) → 1, 1 이 되어 a와 b값을 비교할 수 있다.
즉, a와 b의 비교를 하기위해 자리수를 맞춰주는 작업이라고 생각하면 된다.
