[파이썬] 4880. 토너먼트 카드게임

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

SW Expert Academy

 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.


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

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

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

 

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

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

 

 

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

 

[입력]
 

첫 줄에 테스트 케이스 개수 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

 

# Runtime error
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
def rock_scissor_papper(numbers) :
    _max=0
    for i in numbers :
        if _max < i :
            _max = i
    return _max
    
for test_case in range(1, T + 1):
    N=int(input())
    numbers=list(map(int, input().split()))
    length=N
    
    while length >= 2 :
        length//=2
        if len(A) == 1 :
            print(max(A, B))
            break
        A=rock_scissor_papper(numbers[:length])
        B=rock_scissor_papper(numbers[length:])
        print(A, B)

 

🎈 다른사람 풀이

 

# 가위 바위 보 판별 함수
def win(x, y) :
    # 1은 가위 2는 바위 3은 보
    if (lst[x-1] == 1 and lst[y-1] == 3) or (lst[x-1] == 1 and lst[y-1] ==1) :
        return x
    elif (lst[x-1] == 2 and lst[y-1] ==1) or (lst[x-1] ==2 and lst[y-1] ==2) :
        return x
    elif (lst[x-1] == 3 and lst[y-1] == 2) or (lst[x-1] == 3 and lst[y-1] == 3) :
        return x
    return y

# 수를 나누는 재귀함수
def match(start, end) :
    if start == end :
        return start
    first_value=match(start, (start+end)//2)
    second_value=match((start+end)//2+1, end)
    return win(first_value, second_value)

TC = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for tc in range(1, TC + 1):
    N=int(input())		# 인원수
    lst=list(map(int, input().split()))		# 카드 번호
    start=1
    end=N
    print(f'#{tc} {match(start, end)}')

 

가위 바위 보를 저렇게 일일이 비교하는 조건으로 해야하구나..

처음에 start=1, end=N으로 초기화하고 match함수에서 절반으로 나눈다. return을 하면서 win함수를 호출한다.

x가 이기는 경우만 조건으로 넣었다. 다 false면 y를 반환한다.

 

# 가위 바위 보 판별 함수
def whoWin(a, b) :
    answer=(a-b)%3
    # 0 비김 1 승리 2 패배(a 기준)
    if answer == 1 or answer == 0 :
        return True
    return False

# 수를 나누는 재귀함수
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())
# 여러e개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
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(f'#{t} {result[1]+1}')

 

가위 바위 보 판별이 정말 간단하다

재귀로 수를 나눈다.

두 번째 케이스의 battle함수 실행과정(절반 이후)

1. a_group=[(2, 3), (3, 4)]

b_group=[(3, 5)]

2. a_group=[(2,3)]

b_group=[(3, 4)]

3. a=[(2, 3)]

b=[(3, 4)]

4. whoWin(a[0], b[0]) return b

5. b=[(3, 5)]

6. whoWin(a[0], b[0]) # (3, 4), (3, 5) return a

7. whoWin # (2, 0), (3, 4) return b

8. result=3