Programmers / 예상 대진표 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 예상 대진표 (2단계)

문제 사이트: 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 입니다.)

---

 

입출력 예

N	A	B	answer
8	4	7	3

입출력 예 설명

입출력 예 #1
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

---

나의 풀이

여기서 제한사항으로 부전승은 없다.

 

1.N = 2 (2의 1승)인 경우

2. N= 4 (2의 2승)인 경우

3.N = 8(2의 3승인 경우)

경우가 3가지가 있다.

 

이렇게 N=8에서 N= 2, N=4의 경우를 볼 수 있고 또 해당 범위를 벗어나는 새로운 경우를 볼 수 있다.

 

따라서 해당 내용은 재귀함수가 필요한 식임을 알 수 있다.

 

그러면 대진표에서 순서에따라 A,B가 어느 영역에 속하는지를 알아야 값을 구할 수 있다.

그러면 절반씩 나눠가면서 영역 확인 하면 될듯

 

이 문제를 이해하려면 먼저 리스트를 계속해서 재귀를 이용하여 반으로 잘라 계산하고 검사하는 과정이 필요하다.

예제 [0, 1, 2, 3, 4, 5, 6, 7] 리스트를 계속해서 반으로 자른 값을 저장하여 출력하라.

arr = [i for i in range(8)]
print(arr)
save = []
def solve(n,arr):
    global save # 자른 리스트를 저장하기 위해 선언
    if n == 2:
        return
    arr1 = arr[:n//2] # 리스트를 0~n//2 범위만큼 자른다
    arr2 = arr[n//2:] # 리스트를 n//2 ~ n범위만큼 자른다
    save.append(arr1) # 자른 리스트를 저장
    save.append(arr2) # 자른 리스트를 저장
    print(arr1,arr2)
    solve(n//2,arr1) # 자른 리스트에 대하여 재귀함수 진행(다시 또 절반 자름)
    solve(n//2,arr2) # 자른 리스트에 대하여 재귀함수 진행(다시 또 절반 자름)

solve(8,arr)
print(save)

출력결과

코드를 조금 더 쉽게(1~8까지의 범위)로 맞추어서 해당 출력값을 보면 이렇다.

그러면 파이썬으로 전체 값을 입력해보자!

 

아래 예시는 A=4,B=7일 때 값을 제대로 출력하는지 확인하는 코드이다!

arr = [i for i in range(9)]
arr.pop(0)
print(arr)
save = []
cnt = 0

def solve(n,arr):
    A = 4
    B = 7
    global cnt
    global save
    if n == 2:
        return
    arr1 = arr[:n//2]
    arr2 = arr[n//2:]
    if (A in arr1) and (B in arr2): # 서로 다른 범위에 있는지 확인한다
        print(arr1,arr2)
        return sqrt_solve(n)

    solve(n//2,arr1)
    solve(n//2,arr2)

def sqrt_solve(n): # 지수승을 계산해주는 함수
    cnt = 0
    while n != 1:
        n = n//2
        cnt += 1
    return cnt
print(solve(8,arr))

문제의 의도대로 잘 나온 것을 볼 수 있다.

 

최종 나의 풀이 (30점..)

def solution(n,a,b):
    answer = 0
    arr = [i for i in range(n+1)]
    arr.pop(0)
    A = min(a,b)
    B = max(a,b)
    
    def solve(n,arr):
        
        if n == 2: # n = 2 이면 1번만 경기하므로 1을 반환
            return 1
        
        arr1 = arr[:n//2]
        arr2 = arr[n//2:]
        
        if (A in arr1) and (B in arr2): # 서로 다른 범위에 있는지 확인한다
            cnt = 0
            while n != 1: # 지수승 계산
                n = n//2
                cnt += 1
            return cnt
        solve(n//2,arr1)
        solve(n//2,arr2)
    
    return solve(n,arr)

 

다른 풀이

풀이1) ceil 이용

질문하기에서 a와 b의 값을 ceil 값으로 2로 계속 나눠주면 된다는 내용을 참고한 후 작성한 코드다. 이 풀이가 성립하는 이유는 문제에서 a와 b는 서로 붙게 되기 전까지 항상 이긴다고 가정했기 때문이다.

from math import ceil
def solution(n,a,b):
    answer = 1    # 1라운드에서 시작

    for i in range(n):
    	# a와 b를 다음 라운드 번호로 갱신
        a, b = ceil(a/2), ceil(b/2)
        if a == b: break	# a와 b가 서로 붙음
        answer += 1			# 다음 라운드

    return answer

문제의 입출력 예를 적용해서 살펴보자.
총 참가자는 8명이기 때문에 1라운드에서 서로의 대결 상대는 다음과 같다.

1 vs 2 | 3 vs 4 | 5 vs 6 | 7 vs 8

여기서 4번 참가자와 7번 참가자는 무조건 이겨서 다음 라운드에 진출하기 때문에 다음 라운드에서의 번호는 2번과 4번이 된다. 이 부분이 for 문을 처음 돌았을 때의 상태다. a와 b의 값(참가자의 번호)을 반으로 나누고 올리면 다음 라운드에서의 두 참가자의 번호로 갱신된다.

정리하자면 1라운드에서 a는 4번, b는 7번이다. 2라운드에서 a는 2번, b는 4번이다. 3라운드에서 a와 b 모두 1번이다. 이렇게 a와 b의 값이 같아졌을 때의 라운드(answer)가 결과 값이 된다.

풀이 2) XOR 연산 이용

 

a와 b의 위치를 2진수로 표현했을 때, 서로 가까워지려면 두 비트가 같을 때 0을, 다를 때는 1을 더하는 XOR 연산을 수행하면 된다. (XOR 연산은 서로 다를 때 1을 출력하는 연산이다.)

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

문제의 입출력 예를 적용하여 살펴보면, (a-1)^(b-1)는 3^6이고, 연산 결과는 5가 된다. 여기서 a와 b의 값을 1씩 빼주는 이유는 참가자의 위치를 인덱스 형태로 바꾸는 것이다. 즉, 리스트에서 시작 인덱스가 0이기 때문에 4번째 원소의 인덱스가 3인 것과 같다.

3(4번째 참가자의 인덱스): 011
6(7번째 참가자의 인덱스): 110
XOR 연산 결과: 101 => 5

그리고 bit.length()로 XOR 연산 결과의 길이를 알아낸다. 즉, 이 값이 두 참가자가 만나는 라운드인 셈이다.

 

*풀이 참고 

https://velog.io/@minji0801/%EC%98%A4%EB%8B%B5%EB%85%B8%ED%8A%B8%ED%8C%8C%EC%9D%B4%EC%8D%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%98%88%EC%83%81-%EB%8C%80%EC%A7%84%ED%91%9C

---