[SWEA] 4880. 토너먼트 카드게임 - Python

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

< 📝 문제 >

사다리 게임이 지겨워진 알고리즘 반 학생들이 새로운 게임을 만들었다.

 

가위바위보가 그려진 카드를 이용해 토너먼트로 한 명을 뽑는 것이다. 게임 룰은 다음과 같다.

 

1번부터 N번까지 N명의 학생이 N장의 카드를 나눠 갖는다. 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를

 

비교해서 이긴 사람이 최종 승자가 된다.

그룹의 승자는 그룹 내부를 다시 두 그룹으로 나눠 뽑는데, i번부터 j번까지 속한 그룹은 파이썬 연산으로 다음처럼 두 개

 

로 나눈다.

두 그룹이 각각 1명이 되면 양 쪽의 카드를 비교해 승자를 가리고, 다시 더 큰 그룹의 승자를 뽑는 방식이다.

다음은 4명이 카드를 비교하는 경우로, 숫자 1은 가위, 2는 바위, 3은 보를 나타낸다. 만약 같은 카드인 경우 편의상 번호

 

가 작은 쪽을 승자로 하고, 처음 선택한 카드는 바꾸지 않는다.

N명이 학생들이 카드를 골랐을 때 1등을 찾는 프로그램을 만드시오.

< ❓ 생각 >

⭐ 번호가 인덱스보다 1 크다!!!!!!!

< 💻 코드 >

# 그룹 나누기
def grouping(start, end):
    # 그룹에 1명이 되는경우
    # 예를들어 3명을 grouping하면 1명 / 2명 으로 나누어짐
    if start == end:
        return start

    first_v = grouping(start,(start+end)//2)
    second_v = grouping((start+end)//2+1,end)
    return rcp(first_v,second_v)

# 가위바위보 결과
# 1은 가위, 2는 바위, 3은 보 : 1<2, 2<3, 3<1 
# -> 차이가 1일 때 숫자 큰거, 차이가 2일 때 숫자 작은거 이김
# 같으면 번호 작은 쪽이 이김
def rcp(a,b):
    if arr[a] == arr[b]:
        return a
    elif abs(arr[a]-arr[b]) == 1:
        if arr[a] > arr[b]:
            return a
        else:
            return b
    elif abs(arr[a]-arr[b]) == 2:
        return a if arr[a] < arr[b] else b

# 테스트 케이스
T = int(input())
for tc in range(1,T+1):
    # 인원수
    N = int(input())
    # N명이 고른 카드 번호순
    arr = list((map(int,input().split())))
    start = 0
    end = N-1
    # 번호가 인덱스보다 1개 작음!!!!!
    print(f'#{tc} {grouping(start,end)+1}')

< ❗ 느낀 점 >

그룹을 나누는 과정이 매우 어려웠다... 재귀를 이용하는 것은 아직 익숙지 않아 더 연습해야 할 듯...

번호가 인덱스보다 1 크다는 것을 사용하지 않아 계속 틀렸다.ㅜㅜ