이진 탐색 알고리즘
Q
7795번: 먹을 것인가 먹힐 것인가
심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을
www.acmicpc.net
A
이진 탐색 알고리즘을 쓰는데, bisect 라이브러리를 활용하면 더 쉽게 풀 수 있다.
bisect 사용 코드
from bisect import bisect_left, bisect_right
import sys
testcase = int(sys.stdin.readline().rstrip().split())
for _ in range(testcase):
a, b = map(int, sys.stdin.readline().rstrip().split())
array_a = list(map(int, sys.stdin.readline().rstrip().split()))
array_b = list(map(int, sys.stdin.readline().rstrip().split()))
array_a.sort()
array_b.sort()
result = 0
for i in array_a:
result += bisect_left(array_b, i) #array_b에서 i가 있는 인덱스 출력
print(result)
반복문 코드
import sys
testcase = int(sys.stdin.readline().rstrip().split())
for _ in range(testcase):
a, b = map(int, sys.stdin.readline().rstrip().split())
array_a = list(map(int, sys.stdin.readline().rstrip().split()))
array_b = list(map(int, sys.stdin.readline().rstrip().split()))
array_a.sort()
array_b.sort()
result = 0
j = 0
for k in range(a):
while j < b and array_a[k] > array_b[j]:
j += 1
result += j
print(result)
