백준 파이썬 7795번: 먹을 것인가 먹힐 것인가

tturbo0824 2021. 7. 22. 10:33

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

7795번: 먹을 것인가 먹힐 것인가

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

www.acmicpc.net

문제 유형: 정렬, 이분 탐색, 두 포인터

# Solution 1 - 시간 초과

import sys
input = sys.stdin.readline

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

    count = 0

    for i in range(n):
        for j in range(m):
            if a[i] > b[j]:
                count+= 1
    print(count)

# Solution 2

import sys, bisect

input = sys.stdin.readline

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())))
    count = 0
    for el in a:
        count += (bisect.bisect(b, el - 1))
    print(count)