03/28 알고리즘 공부(80) - 예상 대진표

조건

△△ 게임대회가 개최되었습니다. 이 대회는 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. 한번 승리하게 되면 (번호 + 1) / 2의 번호를 다시 받게 된다.
2. answer의 초기값을 1로 whlie문을 통해 각 선수의 (번호 + 1) / 2, answer ++ 하는 과정을 두 선수의 번호 차이가 1일 때까지 반복한다.
3.  answer를 반환한다.

 

초기 코드

class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {
        var answer = 0
 
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        println("Hello Kotlin")

        return answer
    }
}

 

내 코드

// 실패
class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {
        var answer = 1
        var numA = a
        var numB = b

        while ( numA - numB != 1 && numA - numB != -1){
            numA = (numA + 1) / 2
            numB = (numB + 1) / 2
            answer ++
        }

        return answer
    }
}

테스트 케이스는 통과했으나 채점과정에서 실패가 발생했다. 반복문의 종료조건이 단순히 크기차이가 1이 될 때를 기준으로 했기 때문에 시작번호가 4, 5와 같이 이미 1차 이인경우 이런 문제가 발생한다. 큰 수가 짝수면서 두 수의 차이가 1일 때의 조건을 추가해야겠다.

// 실패(시간초과)
class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {
        var answer = 1
        var numA = a
        var numB = b

        while(true) {
            numA = (numA + 1) / 2
            numB = (numB + 1) / 2
            answer ++
            
            if(numA - numB == 1 && numA % 2 == 0) break
            else if(numB - numA == 1 && numB % 2 == 0) break
        }

        return answer
    }
}

무한루프가 발생해서 시간초과가 뜬다. 위 풀이에서는 발생하지 않았던 것을 보니 종료조건을 아래로 옮기면서 발생한 문제인 것 같다.

class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {
        var answer = 1
        var numA = a
        var numB = b

        while(true) {
            if(numA - numB == 1 && numA % 2 == 0) break
            else if(numB - numA == 1 && numB % 2 == 0) break
            else{
                numA = (numA + 1) / 2
                numB = (numB + 1) / 2
                answer ++
            }
        }

        return answer
    }
}

종료조건을 위로 올려주니 해결됐다. 

다른 사람의 풀이

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

class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {
        var answer = 0
        var x = a
        var y = b
        while (x != y) {
            x = (x + 1) / 2
            y = (y + 1) / 2
            answer++
        }
        return answer
    }
}

개선점 또는 배운점

토너먼트 표

1. 첫 풀이는 볼 때도 충격받고 해석하면서도 충격받았다. xor연산은 앞 뒤의 두 수를 비트로 바꾸어 같은 자릿수에 1이 하나만 있을 때 해당 자리수에 1을, 그 외의 경우에는 0을 반환한다. 같은 자릿수의 값이 다른가를 비교하는 연산자라고 생각하면 좋다. 
   자 이제 이게 어떻게 토너먼트와 연관이 있는가를 생각해 보자.
   1. 토너먼트는 2명이서 겨루기 때문에 각 자리를 비트에 대입해 위쪽자리를 0, 아래쪽 자리를 1이라고 생각하자. 
   2. 문제에서 선수들의 번호는 1부터 시작하기 때문에 각 선수 번호에 1을 빼주어 0부터 시작하게 바꿔준다.
   3. 선수의 번호를 비트로 바꾸는 것은 각 자릿수의 라운드에서 해당 선수가 들어갈 자리를 확인하는 것과 같다.
      
      예를 들어 5번과 7번 자리를  생각해 보자. 예시로 가지고 온 대진표는 8명이므로 4자리까지 표기해 보자
      
      5를 2진수로 바꾸면 0101, 1을 빼면 0100이 된다.
      이 이진수의 첫 번째 자릿수는 0으로 위쪽 자리를, 두 번째 자리도 0이므로 위쪽, 세 번째 자리수는 1이기 때문에 아래쪽 자리를 가지게 된다. (위 위 아래 위)
       
      7을 2진수로 바꾸면 0111, 1을 빼면 0110이 된다.
      이 이진수의 첫 번째 자릿수는 0으로 위쪽, 두 번째 자리는 1이므로 아래쪽, 세 번째 자릿수도 1이기 때문에 아래쪽자리를 가지게 된다. (위 아래 아래 위)
      
      (4 xor 6).toString(2)을 거치면?
      
      0010이 된다. 만약 이 토너먼트가 8자리가 아니라 2^10자리라면 0000000010이 된다. 이게 무슨 뜻이냐면 2번째 경기 이후로는 5번과 7번 두 선수의 자리가 계속 같다는 것이다. 두 선수가 경기를 하기 위해서는 자리가 달라야 한다. 따라서 마지막으로 다른 자리를 가지게 되는 두 번째자릿수, 즉 두번째 라운드에서 경기를 진행하게 된다는 것이다.
      
      length?
      
      컴퓨터는 따로 설정을 해주지 않는 이상 000000010같이 표현하지 않고 10같이 앞의 불필요한 자릿수를 만들지 않는다. 따라서 xor 연산자를 거치고 난 이후의 값은 0010이 아닌 10이 나오게 되어 가장 왼쪽의 1의 자릿수를 길이를 통해 찾을 수 있다.
      
      
2. 아래 풀이는 answer = 0부터 시작해 a와 b의 번호가 같아지는 라운드를 계산했다. 내 방법보다 훨씬 깔끔하다.

 

개선된 코드

class Solution {
    fun solution(n: Int, a: Int, b: Int): Int {
        var answer = 0
        var numA = a
        var numB = b

        while(numA != numB) {
            numA = (numA + 1) / 2
            numB = (numB + 1) / 2
            answer ++
        }

        return answer
    }
}

이 문제로 프로그래머스에서 푼 알고리즘이 100개를 달성했다.