문제 조건

input

• 각 팀의 숫자 배열 A,B
  • 1 ≤ A,B.len ≤ 1,000,000,000

output

• B팀이 얻을 수 있는 최대 승점

문제 해석

• 정렬 + 이진 탐색
  • B를 정렬 후, A를 순회
    • 이때, A보다 큰 가장 작은 값을 계속 탐색
    • 찾았다면, res + 1 해주고 B에서 해당 요소 pop
  • 시간 복잡도 O(n^2)
  • 절반 정도만 통과.. 왜 통과 못하지?
  • 그리고 이진 탐색을 사용하려면 B를 계속 pop해줘야 하는데, 여기서도 O(n) 타임이 소요되어서 어차피 못씀..
• 그리디
  • 시간 복잡도 O(nlogn)
  • ‘최대’와 입력 조건(1,000,000,000) → 완탐 불가.. 그러면 단순 그리디 냄새
  • A,B 모두 정렬하고, A를 순회하면서 B가 이길 수 있는 모든 경우의 수만 체크

코드

1. 이진 탐색

   def solution(A, B):
       B.sort()
       res = 0
       
       for a_num in A:
           s = 0
           e = len(B)-1
           index = 0
           
           while s < e:
               mid = (s+e) // 2
               index = mid
               
               if B[mid] > a_num:
                   e -= 1
               else:
                   s += 1                
           
           if B[index] > a_num:
               res += 1
           
           B.pop(index)
   
       return res 
   

2. 그리디

   def solution(A, B):
       A.sort(reverse=True)  
       B.sort(reverse=True)  
       res = 0
       b_index = 0  
       
       # B에서 A를 이길 수 있는 경우가 몇개인지만 찾으면 됨
       # 이길 수 있으면 다음으로 작은 B의 요소가 이길 수 있는 지 체크
       for a_num in A:
           if B[b_index] > a_num:
               res += 1
               b_index += 1
   
       return res