예상 대진표 Swift

문제 설명

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

---

내가 푼 풀이

참가자 번호 A,B 

N의 지수를 구하고 지수만큼 반복한다.

지수만큼 반복할 때, N을 2로 나눠서 참가자 A,B가 어디 범위에 있는지 조사한다.

N을 2로 나눴을때 양쪽에 존재하는경우, 현재 지수번째 라운드에서 만나게 된다.'

N을 2로 나눴을때 두 참가자가 나눈 값보다 위에 있을때 참가자의 번호에서 나눈값을 빼서 범위 조사에 용이하게 한다.

 

ex) N = 8, A= 4, B= 7, n의 지수 count: 3

count = 3 일때)

• N / 2 = 4 , 4 를 기준으로 A는 4보다 같거나 작고, B는 4보다 크다.
• N/ 2 기준으로 양쪽에 참가자가 있으므로 count = 3 인 3번째 라운드에서 만난다.

 

ex) N = 8, A= 1, B= 2, n의 지수 count: 3

count = 3 일때)

• N / 2 = 4 , 4 를 기준으로 A와 B 둘다 4보다 작다.
• N / 2 = 4 를 기준으로 양쪽에 존재하지 않으므로 count - 1

count = 2 일때)

• N / 2 = 2 , 2 를 기준으로 A와 B 둘다 2보다 작거나 같다.
• N / 2 = 2 를 기준으로 양쪽에 존재하지 않으므로 count - 1

count = 1 일때)

• N / 2 = 1 , 1 를 기준으로 A = 1, B = 2 이므로 A는 1보다 작거나같고, B는 1보다 크다.
• N / 2 = 1 를 기준으로 양쪽에 존재하므로 count  = 1 인 1번째 라운드에서 만난다.

 

만약 A와 B 둘다 n/2 보다 큰경우, N/2 만큼 빼서 대진표의 왼쪽편으로 이동하게 한다.

결국 A와 B가 몇번째 라운드에서 만나는지가 중요하기 때문에, n/2 만큼 빼서 범위계산하기 더 편하게 한다.

 

import Foundation

func solution(_ n:Int, _ a:Int, _ b:Int) -> Int
{
    var num = n
    var numA = a
    var numB = b
    var count = 0
    var result = 0
    while num > 0 {
        num = num / 2
        count += 1
    }
    
    num = n
    
    while count > 0 {
        count -= 1
        var arr = [Int]()
        num = num / 2
        arr.append(numA)
        arr.append(numB)
        
        if arr.filter{ $0 <= num }.count == 1 {
            result = count
            break
        }else if arr.filter{ $0 > num}.count == 2 {
            numA = numA - num
            numB = numB - num
        }
        
    }

    return result
}