[백준] 7795번 : 먹을 것인가 먹힐 것인가

문제

나의 첫번째 제출(시간초과)

import sys
input=sys.stdin.readline
t=int(input())

for _ in range(t):
    cnt=0
    n,m=map(int,input().split())
    a_arr=list(map(int,input().split()))
    b_arr=list(map(int,input().split()))
    for i in b_arr:
        for j in range(len(a_arr)):
            if i<a_arr[j]:
                cnt+=1
    print(cnt)

배열로 각 값을 비교하려고 했으나 시간초과가 났다.
잘못된 알고리즘이라 코드를 다시 짜주었다.

나의 답안

import sys
input=sys.stdin.readline
t=int(input())

def find(a,s,e):
    c=-1#cnt에서 +1을해주었기 때문에 -1로 초기화

    while s<=e:
        mid=(s+e)//2#중간 값(이분탐색)
        
        if a>b_arr[mid]:#a가 b보다 큰 값이라면
            c=mid#인덱스로 초기화
            s=mid+1

        else:#b가 더 크다면
            e=mid-1

    return c

for _ in range(t):
    n,m=map(int,input().split())
    a_arr=list(map(int,input().split()))
    b_arr=list(map(int,input().split()))

    #내림차순 정렬
    a_arr.sort()
    b_arr.sort()

    cnt=0
    
    for i in a_arr:#a에 대해
        cnt+=find(i,0,len(b_arr)-1)+1#가장 큰 수의 인덱스가 0일 경우에 +1
        
    print(cnt)

접근 방법

• b에서 a보다 작은 값 중 가장 큰 값을 찾아야 한다. 이를 위해 이분탐색으로 문제를 풀어준다.
• 이분탐색 풀이를 위해 배열 a, b는 내림차순으로 정렬해준다.
• 가장 큰 값의 인덱스 이후는 모두 b가 더 크고, 그 아래는 a가 더 크다는 것이므로 가장 큰 값의 인덱스가 개수가 된다.
• 이분탐색을 위한 함수를 정의해주고, 해당 함수를 호출할 때 a배열과 시작 인덱스 값, 끝 인덱스 값(b배열의 길이-1)을 전달한다.
  • 이 때, 가장 큰 수의 인덱스가 0일 경우를 대비해 +1을 해준다
  • 따라서 함수안에서 인덱스를 저장할 변수(c)는 -1로 초기화해준다.