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

 문제

 

- 1번부터 N번까지 N명의 학생이 N장의 카드를 나눠 갖는다. 전체를 두 개의 그룹으로 나누고, 그룹의 승자끼리 카드를 비교해서 이긴 사람이 최종 승자가 된다. 그룹의 승자는 그룹 내부를 다시 두 그룹으로 나눠 뽑는다. 기준은 [(i+j)//2 + 1: ]이 된다.

 

 

 

 

 문제 상황

 

- 기저조건까지 리스트를 세분화해서 내려간 뒤 다시 위로 올라오며 조건을 판단한다.

 

 

 

 해결 전략

 

- 숫자 1이 가위, 2, 2는 바위, 3은 보 이므로 조건을 통해 대소비교를 한다.

 

 

 

 코드

 

 
# 가위바위보 조건 만들기
def win(lst, left_idx, right_idx):
    # win이라는 함수는 관찰하는 값이 인덱스이므로 인덱스만을 반환하게 한다.
    # 조건은 리스트의 해당 인덱스의 값으로 비교한다.
    if lst[left_idx] == 1:
        if lst[right_idx] == 1 or lst[right_idx] == 3:
            return left_idx
        else :
            return right_idx
    elif lst[left_idx] == 2:
        if lst[right_idx] == 3:
            return right_idx
        else :
            return left_idx
    else :
        if lst[right_idx] == 1 :
            return right_idx
        else :
            return left_idx
 
# 카드게임 
def cardgame(lst, start, end):
    # 기저조건
    # lst는 조건에서 변하지 않으므로 len(lst)==1 조건 사용 불가
    # 인덱스만 움직이므로 인덱스가 같아질 때, 즉 한 요소만 남았을 때 인덱스를 반환한다.
    if start == end:
        return start
    l_idx = cardgame(lst, start, (start+end)//2)
    r_idx = cardgame(lst, (start+end)//2+1, end)
    # 이긴 쪽 인덱스를 출력한다.
    return win(lst, l_idx, r_idx)
    
    
    
 
# testcase
T = int(input())
 
for idx in range(T):
    # 인원 수 받기
    N = int(input())
    # 카드의 종류 입력받기
    N_list = list(map(int, input().split()))
    result = cardgame(N_list,0,N-1)
    print(f"#{idx+1} {result+1}")
    

 

 

 해설

 

- 다른 사람의 풀이를 참고하였다. 처음에 문제를 잘못 읽어 최종 우승자가 낸 가위, 바위, 보 를 찾았지만 인덱스를 찾는 문제라 더 어려웠다. 무엇을 냈는지를 판별하는 것은 승자, 패자 결정 부분 밖에 없으므로 따로 함수를 만들어 처리해주고 나머지는 인덱스로만 출력하면 된다. 

 

 새로 학습한 것 & 실수 

 

- 함수를 만들 때에 무엇을 입력해서 무엇을 출력해야 하는지 먼저 정의할 필요가 있다. 

 

 

출처 - https://swexpertacademy.com/main/