문제
사다리 게임이 지겨워진 알고리즘 반 학생들이 새로운 게임을 만들었다. 가위바위보가 그려진 카드를 이용해 토너먼트로 한 명을 뽑는 것이다. 게임 룰은 다음과 같다.
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등의 번호를 출력한다.
풀이1
두 그룹으로 나누고 각각의 그룹의 선수들을 가위바위보 시키는데,
0번째 선수와 1번째 선수를 대결시켜서 0번째 선수가 이기면
다음으로 0번째 선수와 2번째 선수를 대결시키는 방법으로 그룹의 마지막 선수까지
대결을 시키는 방식으로 풀이 하려고 했음.
풀이1 코드
T = int(input())
for test_case in range(1,T+1):
N = int(input())
card = list(map(int,input().split()))
main1=card[0] #결승전 올라가는 카드1 첫시작은 index=0
main2=card[round(N/2)] #결승전 올라가는 카드2 첫시작은 index=round(N/2) 홀수까지 고려해서 반올림시킴
main1_index=0 #결승전 올라가는 선수 index1
main2_index=round(N/2) #결승전 올라가는 선수 index2
#결승전 선수고르기 1
result=0#결승 이긴 선수 인덱스 넣을 곳
for i in range(1,round(N/2)):
dif = main1-card[i]
if dif == -1 or dif==2: #뒷사람이 이김
main1=card[i]
main1_index=i
#나머지 경우는 main을 안바꾸면 돼서 안씀.
#결승전 선수고르기2
for i in range(round(N/2)+1,len(card)):
dif = main2-card[i]
if dif == -1 or dif==2: #뒷사람이 이김
main2=card[i]
main2_index=i
#나머지 경우는 main을 안바꾸면 돼서 안씀.
#결승전
dif=main1-main2
if dif == -1 or dif==2: #뒷사람이 이김
result=main2_index
else: #비기거나 앞사람이 이기면 인덱스 앞에꺼를 출력
result=main1_index
print(f"#{test_case} {result+1}")
풀이1 문제점
어째서 인지 hidden case는 정답 처리가 되지 않아 다른방법을 찾아봄.
풀이2
재귀함수로 두 그룹에서 계속 그룹으로 쪼개는 방법을 사용
풀이2 코드
def groupdivide(start,end):
if start==end:
return start
front = groupdivide(start,(start+end)//2)
back = groupdivide((start+end)//2+1,end)
return rsp(front,back)
def rsp(front,back):
dif = card[front]-card[back]
if dif == -1 or dif==2: #뒷사람이 이기는 경우엔 뒤의 인덱스를 반환
return back
else: #나머지는 앞의 인덱스 반환
return front
T = int(input())
for test_case in range(1,T+1):
N = int(input())
card = list(map(int,input().split()))
print(f'#{test_case} {groupdivide(0,N-1)+1}')결론
처음 풀이방법으로 해결하려 했으나, hideen case를 해결하지 못하여
재귀함수를 만들어서 풀이함.
알고리즘은 너무 어렵다...
