[알고리즘] 백준 7795 파이썬 - 먹을 것일가 먹힐 것인가

 

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

문제

심해에는 두 종류의 생명체 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.

문제풀이

for _ in range(int(input())):
    ans=0
    #01
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    b.sort()
    for i in range(n):
    	#02
        if a[i]<=b[0]:
            continue
        elif a[i]>b[m-1]:
            ans+=m
        #03
        else:
            start=0
            end=m-1
            while start+1<end:
                mid=(start+end)//2
                if a[i]>b[mid]:
                    start=mid
                else:
                    end=mid
            ans+=end
    print(ans)

- #01 : 값들을 입력받고 리스트 b는 오름차순 정렬한다.

- #02 : 만약 b의 최소값이 a[i]보다 작거나 같으면 다음 i값으로 넘어가고,

           b의 최대값이 a[i]보다 작으면 ans에 m을 더한다.

- #03 : 그것도 아니라면 이분탐색을 통해, mid값을 변경해가며,

           start+1<end이 될 때까지 while문을 반복한 후 ans에 end를 더한다.

           이후 ans를 출력하고 다음 테스트로 넘어간다.