1. 문제

---

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/7795

2. 아이디어

---

• mine (시간 초과❗)

  1. 정렬 후 b에 있는 가장 큰 숫자부터 시작하여 a의 수 중 현재 b의 숫자보다 큰 수를 만나면 카운트.
     ex) b : 6, a : 8 이면 b에서 6의 인덱스는 2이고 정렬된 (1, 3, 6) 상태이므로 인덱스 + 1 을 해줘서 a의 8보다 작은 b의 숫자를 3으로 카운트.

• clone

  EX) A = [2, 7, 13], B = [11, 103, 215, 290] 일 때
  cnt = 0
  A[0] = 2 -> B에는 2보다 작은 수가 없음 -> res = -1 -> cnt += (-1 + 1) -> cnt = 0
  A[1] = 7 -> B에는 7보다 작은 수가 없음 -> res = -1 -> cnt += (-1 + 1) -> cnt = 0
  A[2] = 13 -> B에서 13보다 작은 수는 2 인덱스는 0 -> res = 0 -> cnt += (0 + 1) -> cnt = 1
  결과: 1

출처 : https://jinho-study.tistory.com/311

3. 코드

---

mine

import sys
input = sys.stdin.readline
t = int(input())
result = []
for i in range(t):
  count = 0
  a, b = map(int, input().split())
  a = list(map(int, input().split()))
  b = list(map(int, input().split()))
  a.sort()
  b.sort()
  for j in a:
    for k in reversed(range(len(b))):
      if j > b[k]:
        count += k + 1
        break
  result.append(count)
for res in result:
  print(res)

clone

import bisect

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 a in A:
        cnt += (bisect.bisect(B, a-1))
    print(cnt)

출처 : https://jinho-study.tistory.com/311