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

SW Expert Academy SWEA 4880 토너먼트 카드게임 문제는 N명의 학생이 가위바위보가 그려진 카드를 나눠갖고, 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 토너먼트로 최종 승자를 가리는 문제이다. 분할 정복 알고리즘에 관한 문제로 난이도는 D2다.

 

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

SW Expert Academy 4880 토너먼트 카드게임 문제 정보

알고리즘 분류

- 분할 정복 알고리즘 Divide and Conquer

난이도

- D2

 

토너먼트 카드게임 문제 요약

• 1번부터 N번까지 N명의 학생이 N장의 카드를 나눠 갖는다. (4≤N≤100)
• 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 이긴 사람이 최종 승자가 된다.
• 그룹의 승자는 그룹 내부를 다시 두 그룹으로 나눠 뽑는데, i번부터 j번까지 속한 그룹은 파이썬 연산으로 다음처럼 두 개로 나눈다.
  
  • i, i+1 ... (i+j)//2  |  (i+j)//2+1 ... j-1, j
• 두 그룹이 각각 1명이 되면 양 쪽의 카드를 비교해 승자를 가리고, 다시 더 큰 그룹의 승자를 뽑는 방식이다.
• 카드의 숫자 1은 가위, 2는 바위, 3은 보를 나타낸다. 만약 같은 카드인 경우 편의상 번호가 작은 쪽을 승자로 하고, 처음 선택한 카드는 바꾸지 않는다.
• N명의 학생들이 카드를 골랐을 때 1등을 찾아 출력한다.

문제 풀이 과정

1. 재귀 함수를 사용하여 그룹을 기준에 따라 두 그룹으로 나누고 각 그룹이 1명이 될 때까지 나눠진 그룹을 또 두 그룹으로 나눈다.
2. 두 그룹이 각각 1명이 되면 가위바위보 게임을 한다.
3. 가위바위보 함수를 실행하여 승자를 리턴하는데, 비기면 번호가 작은 쪽을 승자로 한다.
4. 테스트 케이스 번호, 최종 승자의 번호를 출력한다.

코드 및 설명

• cards [] - N명이 고른 카드를 번호순으로 저장해놓은 리스트
• groups [] - 1번부터 N번 까지 속한 그룹 리스트 (m번째는 m+1번 학생)
• mid - 두 그룹을 나누는 기준 값 (피봇)

# 가위바위보
def rockpaperscissors(f, r):
    # 비겼을 때
    if cards[f] == cards[r]:
        return [f]  # [min(f, r)]
    elif abs(cards[f] - cards[r]) == 1:
        if cards[f] > cards[r]:
            return [f]
        else:
            return [r]
    elif abs(cards[f] - cards[r]) == 2:
        if cards[f] < cards[r]:
            return [f]
        else:
            return [r]

# 그룹 나누기
def divide(group):
    # 그룹이 1명일 때
    if len(group) == 1:
        return group

    # mid를 중심으로 두 그룹으로 나눈다.
    mid = (len(group) - 1) // 2 + 1
    front = group[:mid]
    rear = group[mid:]

    front = divide(front)
    rear = divide(rear)

    return rockpaperscissors(front[0], rear[0])

for tc in range(int(input())):
    N = int(input())
    cards = list(map(int, input().split()))
    groups = list(range(N))

    print('#{} {}'.format(tc + 1, divide(groups)[0] + 1))

---

SW Expert Academy SWEA 4880 토너먼트 카드게임 문제는 분할 정복 Divide and Conquer 알고리즘 활용 문제이며 가위바위보 알고리즘도 파이썬으로 구현하였다. 난이도는 D2인데 해결법을 생각하고 알고리즘을 구현하는데 어려웠다.