[ 프로그래머스 - Kotlin ] 예상 대진표 ( 코틀린 )

( 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 하면 됩니다.

---

[풀이]

토너먼트의 경우 비트 연산을 사용하여 풀면 간단히 해결됩니다.

우선 a와 b에 1을 빼서 2를 나우 었을 경우에 같은 값이 나오도록 합니다.

여기서 확인하고 가야 할 규칙은 아래 그림처럼 초록색 영역 어디든지 a값이 있거나 노란색 영역 어디든지 b값이 있으면 모든 결과는 같습니다.

초록색 영역과 노란색 영억 어디든 값이 있어도 결과는 같음을 보여주는 그림

그럼 아래와 같이 a값이 3이더라도 첫 번째 즉 0 값이라고 생각을 하고 계산을 해도 무관합니다.

아래 그림처럼 a가 0이라고 생각하고 b값을 그대로 6이라고 생각하면 두 개를 xor 하면 나오는 값은 110으로 길이가 3인 이진수가 나옵니다.

여기서 xor연산을 하는 이유는 이진수의 경우 한 칸씩 왼쪽으로 갈수록 2배씩 늘어남으로 가까우면 맨 오른쪽의 값 하나만 다를 것이고 그다음 멀리 있는 값은 2번째 자릿수 즉 4배 멀 것이고 그다음 노란색의 경우 8배 멀어진 자릿수인 3번째 자릿수가 달라질 것임으로 xor를 하여 나온 값의 길이를 반환하는 것입니다.

xor연산을 하는 이유를 그림으로 설명

---

[코드]

class Solution {
    fun solution(n: Int, a: Int, b: Int) = ((a-1) xor (b-1)).toString(2).length
}

문제 링크

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

제가 잘못 알고 있거나 잘못된 부분이 있을 경우 알려주시고 추가로 궁금한 점 있으신 분들도 댓글이나 메일 주시면 성실히 답변해 드리겠습니다.🧑🏻‍💻

감사합니다~😄