[4코1파] #37. 예상 대진표

[4코1파] 4명의 안드로이드 개발자와 1명의 파이썬 개발자의 코딩 테스트 서막 : 4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원

START :

[3코1파] 2023.01.04~ (37일차)
[4코1파] 2023.01.13~ (28일차)

Today :

2023.02.09 [37일차]

프로그래머스 LV2
예상 대진표
https://school.programmers.co.kr/learn/courses/30/lessons/12985

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 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
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

문제 풀이 방법

(1) 첫 번째 시도는 정렬

• 처음에 보고 쉘(shell) sort 를 사용하면 되나? 하고 고민 때림
  

근데 구현이 잘 안됨

(2) 문제를 읽고 두뇌 풀가동하니 2의 지수이야기가 나오는 것을 보기도 하고,
자꾸 2로 끊어지는게 2를 이용해야 할 것 같은 아이디어가 떠오름

근데.. 샤발,,, 규칙을 찾을 듯 못 찾겠음
졌다 졌어~
나는 빠가임

• 그래서 구글링 했는데.. 나는 거의 직전까지 간거임.... 포기하지말자 인간아...
• 2를 이용해서 몫과 나머지를 더한 후에 다음 대진표의 값을 알 수 있었 던 것임!
• 다음 대진 경기 순서가 같으면 멈추고 그것을 return 하는 대로 짜면 되는 아주 손쉬운..
• LV2는 은근히 생각을 많이하게 해놓고 구현은 간단한 그런 문제가 많이 발생하고 있다... 저런..
• 굳이 주어진 인자 argument인 n은.. 저 구현방식으로는 안써도 됐었다.
  하지만 인자가 그냥 주어지진 않았을 터, n을 가지고 구하는 방법이 있겠지..
  구글링 해보니까 이진탐색으로 꽤 복잡하지만 구현에 성공한 사람이 있었다.. .포기하지말고 본받자 그게 네 목표다

내 코드*

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

    return answer

증빙

다른 사람 풀이

• a,b를 xor 취하는 과정에서 a,b 사이의 거리가 가까우면 상위 비트는 차이가 나지않고, 거꾸로 ab 사이의 거리가 멀어지면 상위 비트의 차이가 날 것이다. xor 연산 결과의 길이를 return 해주면 round가 나오는 아이디어로.. 미친 아이디어 이다.
• 각 1을 빼는 것은 선수의 위치를 0-index로 바꾸기 위한 것.. a,b가 각 선수의 위치.. 2비트 수로 표현하여 구한 것...
• 요즘은.. 컴퓨터가 프로그래머스 LV2도 푸나 ?

여담

LV2 푸는 게 나한텐 왜 이렇게 어려운지..
이게 맞는지..

절망의 계곡에서 벗어날 순 없는지