[SWEA 4880][파이썬 S/W 문제해결 기본]. 5일차 - 토너먼트 카드게임

문제

사다리 게임이 지겨워진 알고리즘 반 학생들이 새로운 게임을 만들었다. 가위바위보가 그려진 카드를 이용해 토너먼트로 한 명을 뽑는 것이다. 게임 룰은 다음과 같다.

1번부터 N번까지 N명의 학생이 N장의 카드를 나눠 갖는다. 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 이긴 사람이 최종 승자가 된다.

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

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

다음은 4명이 카드를 비교하는 경우로, 숫자 1은 가위, 2는 바위, 3은 보를 나타낸다. 만약 같은 카드인 경우 편의상 번호가 작은 쪽을 승자로 하고, 처음 선택한 카드는 바꾸지 않는다.

 

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

 

 

 

 

내 생각

생각보다 간단한 문제이다. 근데  나는 분할정복이라는 것에만 갇혀서 멍청한 시간을 보냈다 ㅜㅜ (미리 겁먹지 말자,,)

가장 크게 나누면 3가지로 나눈다.

1. 입력받기
    입력받는건 쉽다. 인원수 N과 고른 카드 입력받기(cards) 

2. 분할정복 함수 (쉽게 말해서 반으로 쪼개기)
    분할정복을 해내야해! 에 갇혀서 꽤나 긴 시간을 보냈지만 분할정복 별거 없다 ! 재귀로 풀어나가는 거 생각하면 그게 바로 분할정복이다.

반으로 쪼개고 또 그 반으로 쪼개고 하는 것이다. 반으로 쪼개기위해서는 반이 어디인지 계산해야한다. ((시작+끝)//2)

반을 기준으로 왼쪽 그룹과 오른쪽 그룹으로 나뉜다. 그리고 이 과정은 한 명이 남을 때까지 계속되어야 한다 → 재귀

3. 토너먼트 함수

    이 함수는 가위바위보를 진행하는 함수이다. 분할정복 함수에서 나눈 그룹을 게임을 시켜야 우승자를 가릴 수 있다고 생각하면 쉽다. 위의 함수에서 나는 그룹을 토너먼트 함수 (game 함수)로 보내서 가위바위보를 시킨다!

가위바위보는 승리, 패배, 무승부의 결과만 있다.

1 = 가위, 2 = 바위, 3 = 보를 나타내므로, 승리하는 건 1>3 and 2>1 and 3>2의 경우가 있다. 또한 숫자가 같다면 비기는 것! : (cards[player1] == 1 and cards[player2] == 3) or (cards[player1] == 2 and cards[player2] == 1) or (cards[player1] == 3 and cards[player2] == 2)

내가 적은 코드와는 다른 방법으로 이 부분은 빼는 것으로도 계산 할 수 있다 ! 즉, 승리하는 경우의 계산은 1-3 = -2, 2-1 = 1, 3-2 = 1이다.  :  cards[player1] - cards[player2] == 1 or cards[player1] - cards[player2] == -2 로도 이긴 경우를 판단할 수 있다!

 

 

 

코드

# 분할정복
def divide(start, end):
    if start == end:
        return start  # 남은 한 명이 1등
    mid = (start + end) // 2
    person1 = divide(start, mid)  # 왼쪽 승자
    person2 = divide(mid + 1, end)  # 오른쪽 승자
    return game(person1, person2)  # 가위바위보

# 가위바위보
def game(player1, player2):
    if cards[player1] == cards[player2]:  #비김
        return player1
    elif (cards[player1] == 1 and cards[player2] == 3) or (cards[player1] == 2 and cards[player2] == 1) or (cards[player1] == 3 and cards[player2] == 2):
        return player1
    return player2

T = int(input()) 
for test_case in range(T):
    N = int(input())  
    cards = list(map(int, input().split()))  
    winner = divide(0, N - 1)  
    print(f'#{test_case + 1} {winner + 1}')