[백준] 7795번: 먹을 것인가 먹힐 것인가 (파이썬)

✅문제: 7795번

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

📌개념정리

(1) 이진 탐색(Binary Search)

• 정의: 정렬된 배열에서 특정한 값을 효율적으로 찾는 탐색 기법
• 탐색 범위를 반으로 줄이면서 값을 찾기 때문에 O(log N)의 시간 복잡도를 가짐.
• 파이썬에서는 bisect 모듈을 사용하여 이진 탐색을 간편하게 구현할 수 있음. 이 모듈은 정렬된 배열에서 요소를 삽입할 위치를 찾거나, 특정 요소의 인덱스를 찾는 함수를 제공함.
• 파이썬에서 bisect 사용
    1. bisect_left(a, x): 값 x를 배열 a에 삽입할 수 있는 가장 왼쪽 위치를 찾아 반환함.
    2. bisect_right(a, x): 값 x를 배열 a에 삽입할 수 있는 가장 오른쪽 위치를 찾아 반환함.

📌문제풀이

배열 A의 각 요소가 배열 B의 몇 개의 요소보다 큰지를 판단하는 문제임. 배열 B를 정렬한 후, 배열 A의 각 요소에 대해 이진 탐색을 사용하여 배열 B에서 해당 요소보다 작은 요소들의 수를 빠르게 찾아야 함.

1. 테스트 케이스 수(T)만큼 반복
2. 각 케이스에 대해 배열 B를 정렬
3. 배열 A의 각 요소(a)에 대해 bisect_left(B, a)를 사용하여 배열 B에서 a 미만의 요소들의 수를 찾음

import sys
import bisect

input = sys.stdin.read
data = input().split()

index = 0
T = int(data[index])	# 테스트 케이스 수
index += 1
results = []

for _ in range(T):
    N = int(data[index])
    M = int(data[index + 1])
    index += 2
    A = list(map(int, data[index:index + N]))
    B = list(map(int, data[index + N:index + N + M]))
    index += N + M

    B.sort()
    count = 0

    for a in A:	# 배열 A의 각 원소에 대해
        pos = bisect.bisect_left(B, a)	# 배열 B에서 a보다 작은 요소의 수를 찾음
        count += pos

    results.append(str(count))

print("\n".join(results))

📌후기

• 파이썬의 bisect 모듈이라는 것을 알고 사용해보면서, 앞으로 정렬된 배열에서 위치를 찾는 다양한 상황에 유용하게 사용할 수 있을 것 같음.
• 파이썬의 편리한 기능들이 많다는 것을 다시 한번 깨닫고, 알고리즘 문제 해결 시 자주 사용되는 모듈을 숙지해야겠다고 생각함.

📌참고자료

1) Python Docs, "bisect — 배열 이진 분할 알고리즘", https://docs.python.org/ko/3.10/library/bisect.html