[Python] 7795번 먹을 것인가 먹힐 것인가

✏️ 문제

 

문제 파악

처음에는 a 배열을 기준으로 이분 탐색을 하려했는데 생각해보니 a 배열의 각 요소가 b 배열의 요소보다 큰 지 안 큰 지에 대해서 정답을 구하는 것이므로 b 배열을 기준으로 이분 탐색을 하는 것이 맞다!

이분 탐색을 하기 위해선 배열이 정렬되어 있어야한다. 

위의 예시를 보면 쌍의 개수는 b 배열의 인덱스+1 한 값과 같다는 걸 알 수 있다.

while ...
   if b[mid] < a[i]:
        start = mid + 1
    else:
        end = mid - 1

cnt += end + 1

 

또한 큰 쌍의 개수를 구하므로 end + 1을 해주어야 한다.

 

알고리즘

• 두 포인터
• 정렬
• 이분 탐색

 

 

코드

for _ in range(int(input())):
  n,m = map(int, input().split())
  a = sorted(list(map(int, input().split())))
  b = sorted(list(map(int, input().split())))
  cnt = 0

  for i in range(n):
    start, end = 0, m-1

    while start <= end:
      mid = (start + end) // 2

      if b[mid] < a[i]:
        start = mid + 1
      else:
        end = mid - 1
    
    cnt += end + 1

  print(cnt)