[ baekjoon ] 먹을 것인가 먹힐 것인가 7795번 ( python )

문제

백준 7795 먹을 것인가 먹힐 것인가 풀이 ( 파이썬 )

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

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

 

풀이

처음에는 아래 코드처럼 큰 걸 발견했을 때 cnt를 증가시키도록 했지만 시간초과가 떴다.

import sys

input = sys.stdin.readline

t = int(input())

while t:

    cnt = 0

    n, m = map(int, input().split())

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    for i in A:
        for j in B:
            if i > j:
                cnt+=1
    
    print(cnt)

    t-=1

 

그래서 정렬을 한 후 이분탐색으로 풀었다.

import sys
import bisect

input = sys.stdin.readline

t = int(input())

while t:

    cnt = 0

    n, m = map(int, input().split())

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    A.sort()
    B.sort()

    for i in A:
        cnt += bisect.bisect_left(B, i)
    
    print(cnt)
    t-=1