백준 1057번. 토너먼트 (Java)

문제 링크 : https://www.acmicpc.net/problem/1057

김지민, 임한수가 라운드 몇에서 대결하게 될 지 맞추는 문제입니다.

처음에 단순하게 Queue로 구현을 하였습니다.

1. 모든 토너먼트 멤버를 Queue에 넣은 뒤 두 개씩 poll 한다.

2. 두 값을 비교하여 김지민, 임한수라면 라운드를 출력하고 종료

2-1. 두 값 중 하나만 김지민 혹은 임한수라면 무조건 승리자

2-2. 둘 다 해당되지 않는다면 무조건 앞 번호가 승리자

이렇게 단순하게 구현하여 Queue에 계속 넣었다 빼며 구현하였습니다.

하지만 정답을 맞춘 후에 다른 정답자들 코드를 보니 굉장히 간단하게 구현하였습니다.

각 멤버가 같은 라운드에서 만난다는 것은 부모 노드가 같다고 볼 수 있습니다.

그래서 두 멤버의 부모 노드만을 계속 따라가며 같은 값이 될 때의 라운드를 출력하면 됩니다.

자식 노드가 최대 두 개로 고정되어 있기 때문에 부모 노드의 인덱스는

(now + 1) / 2

now/2 + now%2

이렇게 두 가지 방법으로 구할 수 있습니다.

코드는 처음에 구현했던 Queue를 이용한 방법과 두번째로 구현한 방법 모두 올리겠습니다.