[프로그래머스] Lv.2 예상 대진표

구현 & 수학

https://school.programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

 

코드

def solution(n,a,b):
    answer = 1
    while n > 0:
    
        answer += 1
        if a % 2 == 0:
            if a - 1 == b:
                break
        else:
            if a + 1 == b:
                break
        

        a, b = (a // 2) + (a % 2), (b//2) + (b % 2)
    
        n //= 2

    return answer-1

 

설명

 대진표를 구성하는 문제다. 정확히 말하면 대진표에서 a, b가 만나는 라운드의 회차를 구하는 문제가 된다. 이 문제는 아이디어를 떠올리는 게 흥미로웠던 문제 같았다. 초반에 주석을 달아가며 생각을 정리하던 중 몇 가지 아이디어를 발견했는데 우선 대진표는 2^20 지수승으로 주어진다는 것. 결국 밑이 2기 때문에 홀수로 주어지는 경우가 존재하지 않는다. 따라서 조건에서도 명시했듯이 부전승은 존재하지 않는다. 부전승이란 매칭이 전부 1:1로 맞추어졌을 때 홀수명의 사람들이기 때문에 홀수명의 사람이 남게 되면 즉 한 명이 남게 되면 그 사람은 부전승이라고 하여 경기를 하지 않고 올라가는 걸 의미한다. 하지만 위에서 이미 언급했듯이 지수승으로 주어졌기 때문에 부전승은 없다.

 

 그렇다면 모두 1:1 매칭이 된다는 것이고 문제에서 주어지는건 n명의 사람 그리고 a, b의 번호다. a, b는 서로가 만나기 전까지는 무조건 계속 이긴다고 가정한다고 했으므로 1번부터 N번까지 번호가 주어졌을 때 a, b의 번호는 짝수와 홀수일 때로 생각해 본다면 코드에서 보이는 식과 같이 구할 수 있게 된다. 왜 저렇게 구해지는 게 가능할까 짝수승으로 주어지는 n명의 사람들은 무조건 1:1로 매칭이 되게 된다. 즉 2명이 한 그룹으로 묶이게 된다는 것이다. 만약 n이 8명이라면 4명의 그룹이 생긴다는 얘기가 된다. 4명의 그룹이 생기게 되면 각 그룹에서는 1명의 사람만이 승리하여 다음 라운드로 올라가게 된다. 그렇다는 건 첫 번째 라운드에서 8명인 사람들이 다음 라운드 두 번째 라운드로 넘어가게 된다면 n명은 절반으로 줄어들게 된다. 따라서 n//2 만큼 줄어들게 된다는 것이다. 그럼 또 n이 절반으로 줄어들게 되고 결국 마지막 한 명이 남을 때까지 줄어들게 된다. (n=2이고 n // 2로 나누게 된다면 1이 되기 때문에) 자 그러면 라운드가 최대 몇 번까지 진행되게 되는지는 구할 수 있게 되었다. 따라서 최악의 경우 n=1명까지 남을 때까지 진행이 될 수 있다는 걸 의미한다. 이 말은 즉 n=2명일 때 서로 만나게 된다는 걸 의미한다. 하지만 항상 최악의 경우에서 끝나는 게 아니기 때문에 그전에 끝날 수 있다. 예를 들어 첫 라운드에서 a의 번호는 1번, b의 번호는 2번이라고 가정한다면 이들은 첫 라운드에서 만나게 되어 첫 라운드에 만나는 게 정답이 된다. 그렇기 때문에 최악의 경우 전에 종료될 수 있다. 그럼 이제 만나는 건 어떻게 처리를 해야 하는 걸까를 생각해 볼 수 있다. 여기서 약간의 규칙을 찾아볼 수 있는데 아래와 같다.

 

 

만약 현재 번호가 홀수라면 홀수인 번호일때는 짝수인 사람과 대결하게 된다.

반대로 현재 번호가 짝수라면 홀수인 사람과 대결 하게 된다.

예를 들어보자.

 

[1,2,3,4,5,6,7,8]

 

8명의 사람이 존재할 때 1은 홀수다 1번은 2번이랑 대결한다. 2는 짝수다.

반대로 2는 짝수다. 짝수일때짝수일 때 1은 홀수다. 따라서 짝수일 때 홀수랑 대결한다.

 

 

 처음에는 짝수 홀수 따지지 않고 둘중에 한 명만 골라 a-1 혹은 b-1 혹은 a+1 혹은 b+1일 때 라운드를 종료하게 했었다. 하지만 이는 반례가 당연히 존재했고 그 반례가 위 예시다 만약 a가 2이고 b가 3이라면 a!=b라는 조건은 만족하지만  a는 홀수인 사람과 대결하게 되고 b는 짝수인 사람과 대결하게 된다. 그렇다면 짝수 홀수를 따지지 않고 위 코드대로 하면 뭐가 잘못된 걸까? 바로 a+1일 때 b랑 붙게 된다. 근데 이상하지 않은가? 앞에서부터 매칭을 하게 된다면 1번은 2번 3번은 4번이랑 대결해야 정상적인 대진표 루트가 만들어지는데 a+1이 3이 되었기 때문에 2와 3이 매칭이 돼버린다. 그럼 결국 다음 4, 5가 매칭되고 이렇게 매칭되면 맨 처음과 맨 끝 사람은 매칭이 되지 않게 된다. 이는 문제에서 요구하는 매칭 조건이 아니기 때문에 틀린 코드인 것이다. 실제로 88.2점 정도로 몇 개의 케이스들이 틀리는 걸 볼 수 있다. 따라서 조건을 만족하기 위해서 짝수일 때 홀수일 때 구분하여 짝수라면 자기보다 1 작은 사람과 매칭이 되어야 하며 그때 서로가 대결하는 순간이면 종료하는 것이다. 마찬가지로 홀수일 때도 똑같다.