1. 요약
토너먼트 대회에서 A번 참가자가 B번 참가자를 몇 번째 라운드에서 만나는지 구하는 문제.
2. 아이디어
참가자의 수가 항상 2의 지수 승이기 때문에,
Queue를 이용해서 간단하게 풀 수 있다.
Queue에서 참가자 2명을 가져온다.(i.e.popleft()를 2번 시행) 그리고Queue에 참가자가 없을 때까지, 다음을 시행한다.
- 참가자 2명 중 1명이 A번 참가자면 라운드를 하나 증가시키고 A번 참가자를
Queue에 넣는다.- 2명 중 1명이 B번 참가자라면 B번 참가자만
Queue에 넣는다.- 2명이 A번 참가자와 B번 참가자이면, 라운드를 하나 증가시키고 라운드를 반환한다.
- 그 외 경우, 임의의 참가자 1명을
Queue에 넣는다.다시 말해, A번 참가자와 B번참가자가 서로 만날때 까지,
Queue에서popleft를 2번하고 그 중 1명을Queue에append하는 것이다.
3. 코드
from collections import deque
def solution(n,a,b):
q = [i for i in range(1,n+1)]
q = deque(q)
answer = 0
while q:
x = q.popleft()
y = q.popleft()
if [x, y] == [a, b] or [x, y] ==[b, a]:
answer += 1
break
if a in [x, y]:
answer += 1
q.append(a)
elif b in [x, y]: q.append(b)
else: q.append(x)
return answer