[프로그래머스] 예상 대진표 .with 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 입니다.)
•  

-------------------- 내 생각의 흐름 --------------------

 

1. n이 2의 몇승인지 구함 ex) n = 8일때 3

2. a와 b 정렬로 a가 작은수 b가 큰수로 변경

3. 0...n/2 사이에 a가 있는지 확인

4. n/2...n까지 b가 있는지 확인

5. 범위가 서로 다르면 결승전까지 가야하니깐 범위가 다를때까지 n = n/2로 바꾸고 반복

6. 범위가 달라질때까지 몇번반복했는지 구한다음 n이 몇승인지 구한 값에서 빼고 결과 도출

func solution(_ n:Int, _ a:Int, _ b:Int) -> Int
{
    var num = n
    var count = 0
    var square = whatSquare(n)
    var num1 = a
    var num2 = b
    var changeNum = 0
    if num2 < num1 {
        changeNum = num1
        num1 = num2
        num2 = changeNum
    }
    while true{
        var half = num / 2
        if (num1 <= half && half < num2){
            break
        }else{
            num /= 2
            count += 1
        }
    }
    return square - count
}
func whatSquare(_ num: Int) -> Int{
    var result = 0
    var number = num
    while number % 2 == 0 {
        number /= 2
        result += 1
    }
    return result
}

 

이런식으로 만들었는데 whatSquare의 경우에는 몇 승인지 구하는 부분이고

나머지는 위의 설명과 같다.

그러나 프로그래머스에서 정답률은 57%정도 나왔는데

틀린 부분은 전부 성능의 문제였다.

 

다른 사람들의 풀이를 참고해 봐야하는 문제가 등장했다...

 

-----------------------------------------------------------------

다른 분들의 풀이를 보고 수정한사항들이다.

처음 접근을 할때 애초에 다르게 접근을 하여 내 로직의 문제점을 발견하기는 어려웠다.

다만 저 기존의 내 로직을 생각하다 왜 성능관련한 문제가 나왔을까 생각을 하다 깨달았다.

나의 로직은 A와 B를 결승전에 올려서 만나는 것으로 생각을 했다

그래서 A와 B가 n의 절반의 기준으로 다른범위에 있다면 결승전에서 만날수 밖에 없는 것이다.

그렇다면 그 범위를 점차 줄여나가면 되지않을까? 하는 생각으로 짰던 코드인데

내가 구현한 코드의 경우에는 A와 B가 둘이 다른 범위에 있을때와 AB가 둘다 절반보다 작을때의 케이스만 적용되었다

둘다 n/2보다 큰 수가 파라미터로 들어가면 무한 루프가되어버린것...

그렇다면 그 케이스가 추가되어야하는데 그런것 보다는 조금 더 깔끔한 케이스가 있어 가져와 봤다.

func solution1(_ n: Int, _ a: Int, _ b: Int) -> Int {
    var num1 = a
    var num2 = b
    var round = 0
    
    // 두 참가자가 같은 그룹에 속할 때까지 반복
    while num1 != num2 {
        // 참가자 번호를 다음 라운드의 번호로 갱신
        num1 = (num1 + 1) / 2
        num2 = (num2 + 1) / 2
        round += 1
    }
    
    return round
}
 

 

이 경우에는 몇승인지도 필요없고 결승에서 만난다는 것도 필요없다. 다만 동일하게 2를 나누어서 같은 값이 될때 만날 수 있다는 점만 생각하고 만든 로직이기 때문에 해당 부분이 가장 성능적으로도 좋은 로직이지 않을까 싶다.