Programmers - 숫자 게임

문제 링크

N이 최대 10만이라 모든 경우의 수를 탐색하는 것은 불가능하다.
따라서 Greedy로 시도해보았는데 풀렸다.

B팀의 전략 : 이길 수 있으면 가장 적은 점수 차이로 이긴다.

정렬을 하지 않고 가장 적은 점수 차이로 이길 수 있는 숫자를 매번 찾으면 O(n^2)이 되기 때문에
사전에 정렬을 해놓고 A와 B의 인덱스를 증가시키면서 이길 수 있는 경우를 구하면 가장 적은 점수 차이로
이기는 횟수를 구할 수 있다.

def solution(A, B):
    n = len(A)
    A.sort()
    B.sort()

    i = 0
    j = 0
    wins = 0
    while j < n:
        if A[i] < B[j]:
            wins += 1
        else:
            j += 1
            continue
        i += 1
        j += 1

    return wins