[python] algospot MatchOrder 문제풀이

문제

전세계 최대의 프로그래밍 대회 알고스팟 컵의 결승전이 이틀 앞으로 다가왔습니다. 각 팀은 n명씩의 프로 코더들로 구성되어 있으며, 결승전에서는 각 선수가 한 번씩 출전해 1:1 경기를 벌여 더 많은 승리를 가져가는 팀이 최종적으로 우승하게 됩니다.

이 대회에서는 각 선수의 실력을 레이팅(rating)으로 표현합니다. 문제를 간단히 하기 위해 1:1 승부에서는 항상 레이팅이 더 높은 선수가 승리하고, 레이팅이 같을 경우 우리 선수가 승리한다고 가정합시다.

상대 팀의 출전 순서를 알고 있을 때 , 어느 순서대로 선수들을 내보내야 승수를 최대화할 수 있을까요?

 

문제풀이

상대방과의 경기에서 이길 때, 상대 레이팅보다 높은 팀원 중에서 레이팅에서는 가장 작은 사람이 출전해서 이길 때 최선이다.

즉, 항상 우리팀이 적팀의 상대보다 근소한 레이팅 차이로 이기기만 하면 최대 승이 나온다.

 

상대 팀과 우리 팀을 각각 레이팅을 오름차순으로 정렬해 놓는다. 

서로 레이팅이 낮은 애들부터 비교한다. 우리 팀이 레이팅이 더 높다면 두 선수를 매칭시켜 승리를 챙긴다.

만약 상대 팀이 레이팅이 더 높다면 현재 가리키고 있는 우리 팀 선수를 맨 뒤로 보내 가장 레이팅이 높은 사람과 매칭 시킨다.

이때 원래 레이팅 순으로 매칭되어 있던 적이 바뀌게 된다.

하지만 우리 팀의 입장에서 우리팀의 i번째로 약한 사람과 적팀의 i번째로 약한 사람의 매칭에서 

우리 팀의 i-1번째로 약한 사람과 적팀의 i번째로 약한 사람과의 매칭으로 변하게 되므로

승리가 늘어날 수는 있어도 패배가 늘어나는 경우는 존재하지 않게 된다.

 

코드

import sys

# 1개
T = int(sys.stdin.readline().rstrip())

for _ in range(T) :
    N = int(sys.stdin.readline().rstrip())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    B = list(map(int,sys.stdin.readline().rstrip().split()))
	
    # 적팀
    A = sorted(A)
    # 우리팀
    B = sorted(B)
    
    idx_A = 0
    idx_B = 0

    while idx_B < len(B) :
		# 우리팀이 더 높다면 인덱스가 같이 증가한다. == 매칭시킨다.
        if A[idx_A] <= B[idx_B] :
            idx_A += 1
            idx_B += 1
		# 적팀이 더 높다면 우리팀의 상대를 바꿔준다.
        else :
            idx_B += 1
	
    # 적팀이 더 높아서 뛰어넘은 우리 팀원은 더 높은 상대와 만나기에 이길 가능성이 없다.
    # 이길 수 있는 사람의 수만 세주면 최대 승이 된다.
    print(idx_A)

 

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.