(Python/파이썬) - 백준(BOJ) 7795번 : 먹을 것인가 먹힐 것인가

 

https://www.acmicpc.net/problem/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)

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

 

 

 

---

• 풀이 :

테스트 케이스의 최대 횟수가 A, B 모두 20,000 이므로 O(N^2)로 예상되는 완전탐색으로 해결해도 풀린다. 그러나 이분탐색을 사용하면 더 빠르게 해결할 수 있으므로 이분탐색을 활용하여 해결하였다.

 

0. A,B 모두 오름차순 정렬

1. A의 모든 원소에 대해 이분탐색을 실시한다. 이 때, 원소가 B의 0번째 원소보다 작다면 탐색을 실시하지 않는다.

2. 내가 탐색하려는 수가 B[mid]값보다 크다면 result에 mid 값을 넣어주고 아니라면 포인터 범위를 조절한다.

 

 

 

 

 

---

• 소스코드 : 

def binarySearch(a):
    start = 0
    end = M-1
    result = 0
    while start <= end:
        mid = (start+end) // 2
        if B[mid] < a:
            start = mid + 1
            result = mid
        else:
            end = mid-1
    return result + 1

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())))
    answer = 0
    for i in A:
        if i > B[0]:
            t =  binarySearch(i)
            answer += t
    print(answer)