[프로그래머스][LV.2] 예상 대진표 | python3

문제링크:  예상 대진표

---

문제설명

△△ 게임대회가 개최되었습니다. 이 대회는 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)//2 가 됨. 그래서 한 게임이 끝날때마다  a와 b의 자리가 바뀌고 a와 b가 바로 옆에 붙어있을때 붙는다고 생각을 하여 코드를 짰다.

def solution(n,a,b):
    answer = 0
    chk=0
    while n!=1:
        answer+=1
        if abs(a-b)==1:
            break
        a=(a+1)//2
        b=(b+1)//2
        
    return answer

 

근데 4개(7,9,27,33)의 테스트케이스에서 에러가 났다.

그러고 생각해보니 바로 옆에 붙어있어도 8,9 이런식으로 붙어있으면 바로 옆에 있어도 경쟁하지 않는다. 둘 중 작은 수가 홀수여야 한다.

나의코드

def solution(n,a,b):
    answer = 0
    chk=0
    while n!=1:
        answer+=1
        if abs(a-b)==1:
            if min(a,b)%2:
                break
        a=(a+1)//2
        b=(b+1)//2
        
    return answer

 

---

 

참고하기

def solution(n,a,b):
    return ((a-1)^(b-1)).bit_length()

이것 뭐에요...?

 

매번 2로 나누니까 이진수로 치면 매번 오른쪽으로 1비트씩 이동하는 것과 같다.

1. 토너먼트에서 A와 B의 번호 변화

토너먼트에서는 각 참가자의 번호가 매 라운드마다 아래 규칙에 따라 변해:

• 새 번호 = (현재 번호 + 1) // 2
• 예를 들어:
  • 1 2 3 4 5 6 7 8 (1라운드)
  • 1 1 2 2 3 3 4 4 (2라운드)
  • 1 1 2 2 (3라운드)
  • 1 1 (4라운드)
  • 1 (최종 승자)

즉, 각 번호는 매 라운드마다 오른쪽으로 1비트씩 이동하는 것과 동일하게 작동해.

---

2. A와 B가 만나기 직전까지 같은 라운드에서 살아남음

A와 B는 각 라운드에서 같은 방식으로 번호를 계속 바꾸며 진행돼.
그러다가 어느 라운드에서 처음으로 같은 번호를 받는 순간이 바로 대결이 이루어지는 라운드야.

• 예를 들어, A=5, B=8이면:
  • 5 → 3 → 2 → 1
  • 8 → 4 → 2 → 1
  • 3라운드에서 처음 같은 번호가 됨! (따라서 답은 3)

---

3. XOR의 의미

이제 **XOR (^)**을 왜 사용하는지 보자.

• (A-1) ^ (B-1)을 계산하면 A와 B가 처음으로 다른 비트가 나타나는 위치를 찾을 수 있어.
• 숫자를 2진수로 보면, XOR은 각 자리에서 다르면 1, 같으면 0을 반환해.
• 가장 높은 자리의 1이 A와 B가 몇 번째 라운드까지 서로 다른 번호를 받았는지를 알려줘.

예제: A=5, B=8

1. 2진수 변환 (A-1, B-1)
   • A-1 = 4 → 100
   • B-1 = 7 → 111
2. XOR 연산 (100 ^ 111)
   • 100
   • 111
   • ---
   • 011 (3)
3. bit_length()를 적용하면 가장 높은 비트 위치를 반환
   • 011 → 가장 높은 1이 있는 자리는 2번째 (0부터 시작)
   • bit_length()를 적용하면 3이 나옴 → 3라운드에서 만남!

---

4. XOR이 토너먼트 라운드와 정확히 일치하는 이유

1. A와 B가 처음으로 같은 번호를 받는 순간을 찾는 것이 목표야.
2. A와 B의 최상위 다른 비트가 존재하는 위치가 바로 서로 다른 라운드에서 번호가 바뀐 마지막 순간이야.
3. bit_length()는 가장 높은 1이 있는 비트 위치를 반환하는데, 이는 서로 다른 번호를 가졌던 마지막 라운드가 몇 번째인지를 정확히 알려줘.

---

5. 예제 테스트

ABA-1 (2진수)B-1 (2진수)(A-1) ^ (B-1)bit_length()라운드

4	7	011	110	101	3	3
5	8	100	111	011	3	3
1	16	0000	1111	1111	4	4
8	9	0111	1000	1111	4	4

---

6. 결론

• XOR을 사용하면 A와 B가 언제 처음으로 같은 번호를 받는지를 확인할 수 있어.
• bit_length()를 적용하면 최상위 비트 위치를 반환하므로, 몇 번째 라운드에서 만나는지를 정확히 계산 가능.
• 이 방법은 반복문 없이 O(1) 시간에 계산할 수 있어서 매우 효율적!

---

왜 a-1과 b-1일까

 

1. 문제의 핵심: 번호는 1부터 시작하지만, 비트 연산은 0부터 시작하는 것이 편리함

• 문제에서는 참가자 번호가 1, 2, 3, ... N으로 주어져.
• 그런데 토너먼트에서 번호 변화를 보면, 이진수의 특성과 잘 맞아떨어짐.

예제: N=8, A=1~8일 때 변화를 보면

원래 번호2진수1라운드 후2라운드 후3라운드 후

1	001	1	1	1
2	010	1	1	1
3	011	2	2	1
4	100	2	2	1
5	101	3	3	2
6	110	3	3	2
7	111	4	4	2
8	1000	4	4	2

• 각 번호를 2진수로 보면, 매 라운드마다 오른쪽으로 1비트씩 이동하는 것과 같다.
• 그런데, 1번부터 시작하면 이진수 처리가 어색해.
• 그래서 모든 번호를 0부터 시작하는 숫자로 변환하면 편해진다.

---

2. A와 B를 0부터 시작하는 인덱스로 변환

1. 기존 번호 (1부터 시작)
   • A=5, B=8을 예로 들어보자.
   • 5는 101, 8은 1000 (2진수)
2. 0부터 시작하도록 변환 (A-1, B-1)
   • A-1 = 4 (100)
   • B-1 = 7 (111)
3. 이제 XOR을 수행
   • 4 ^ 7 = 3 (011)
   • bit_length() = 3 → 3라운드에서 만난다!

---

3. -1을 하지 않으면 왜 안 될까?

만약 A와 B를 그대로 XOR하면?

• A=5, B=8 → 5 ^ 8
  • 5 = 101
  • 8 = 1000
  • 5 ^ 8 = 1101
  • bit_length() = 4 (잘못된 값)

즉, A와 B가 1부터 시작하기 때문에, 그냥 XOR을 하면 불필요한 추가 비트가 발생해.
-1을 하면 자연스럽게 0부터 시작하게 되어, 비트 변화를 깔끔하게 추적할 수 있다.

---

4. 직관적인 정리

• XOR은 두 숫자가 처음으로 달라지는 비트 위치를 찾는다.
• A, B가 1부터 시작하면 비트 계산이 어색하므로, 0부터 시작하도록 -1을 해준다.
• 이제 XOR 결과의 bit_length()가 곧 A와 B가 처음 만나는 라운드가 된다.

---

5. 결론

-1을 하는 이유는 토너먼트 번호를 "0부터 시작하는 인덱스"로 변환하기 위해서야!
이렇게 하면 비트 연산을 직관적으로 적용할 수 있고, XOR로 쉽게 라운드를 구할 수 있어. 🚀

 

 

def solution(n,a,b):
    answer = 0
    while a != b:
        answer += 1
        a, b = (a+1)//2, (b+1)//2

    return answer

나처럼 1차이날때 말고 (자기자리+1)//2 로 나누었을때 두 수가 같으면 두 수가 바로 옆에 있는 것.

그러니 그냥 a==b로 조건을 걸면 된다.

 

def solution(n,a,b):
    i = 0
    while (a-1)//(2**i) != (b-1)//(2**i):
        i += 1
    return i

위의 비슷한 논리를 while 조건으로 한번에 코딩함.