토너먼트 카드게임 Python(SW Expert Academy)

난이도 : D2

문제번호 : 4880

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIc7KqfQDFAWg#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

사다리 게임이 지겨워진 알고리즘 반 학생들이 새로운 게임을 만들었다. 가위바위보가 그려진 카드를 이용해 토너먼트로 한 명을 뽑는 것이다. 게임 룰은 다음과 같다.   1번부터 N번까지 N명의 학생이 N장의 카드를 나눠 갖는다. 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 이긴 사람이 최종 승자가 된다. 그룹의 승자는 그룹 내부를 다시 두 그룹으로 나눠 뽑는데, i번부터 j번까지 속한 그룹은 파이썬 연산으로 그림1 처럼 두개로 나눈다. 두 그룹이 각각 1명이 되면 양 쪽의 카드를 비교해 승자를 가리고, 다시 더 큰 그룹의 승자를 뽑는 방식이다. 다음은 4명이 카드를 비교하는 경우로, 숫자 1은 가위, 2는 바위, 3은 보를 나타낸다. 만약 같은 카드인 경우 편의상 번호가 작은 쪽을 승자로 하고, 처음 선택한 카드는 바꾸지 않는다. N명이 학생들이 카드를 골랐을 때 1등을 찾는 프로그램을 만드시오.

그림1

그림2

 

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50 다음 줄부터 테스트 케이스의 별로 인원수 N과 다음 줄에 N명이 고른 카드가 번호순으로 주어진다. 4≤N≤100 카드의 숫자는 각각 1은 가위, 2는 바위, 3은 보를 나타낸다.

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 1등의 번호를 출력한다.

예시

입력	출력
3 4 1 3 2 1 6 2 1 1 2 3 3 7 1 3 3 3 1 1 3	#1 3 #2 5 #3 1

---

2. 문제풀이

파이썬 스택 2일차 연습문제 중 하나인 토너먼트 카드 게임 문제이다. D2문제임에도 불구하고 문제를 이해함에 있어서 오래걸려 약간 힘들었던 문제다. 삽질 1 : 처음에는 그룹을 한번만 나누면 되는줄 알았다. 그룹을 한번만 나눈후 대결이 성립하지 못하는인원들은 부전승으로 올려 계산했다.   이문제의 핵심은 계속해서 쪼개서 대결을하고 위로 올려보는것이 핵심이었다. 따라서 재귀함수를 이용한 2진탐색마냥 반절로 쪼개며 계산하여 위로올라가는 형식으로 해결하였다. 그룹인원이 1명이 된다면 자기자신을 리턴하게되고 그위에 단계는 2명이되므로 서로 가위바위보를 하여 승자가 위로 계속 올라가는 형식이 된다.

 

---

3. 소스코드

#4880 D2 토너먼트 카드게임
 
# 1 : 가위,  2 : 바위,  3 : 보
#같은카드일시 작은번호가 승자
 
#가위바위보 승자찾기
#이기거나 비기면 작은번호가 승리
def whoWin(a, b):
    answer = (a - b) % 3
    # 0 비김 1 승리 2 패배(a 기준)
    if answer == 1 or answer == 0:
        return True
    return False
 
#그룹을 계속쪼개서 계산한다.
#작은번호를 a 에 넣고 계산한다.
def battle(group):
    if len(group) < 2:
        return group[0]
    a_group, b_group = [], []
    j = len(group)
    for i in range(j):
        if i <= (j-1)//2:
            a_group.append(group[i])
        else :  b_group.append(group[i])
    a = battle(a_group)
    b = battle(b_group)
    if whoWin(a[0], b[0]): return a
    else: return b
 
 
T = int(input())
for t in range(1, T+1):
    N = int(input())
    player = list(map(int, input().split()))
    player = [(i, idx) for idx, i in enumerate(player)]
    result = battle(player)
    print('#{} {}'.format(t, result[1]+1))