[백준(파이썬/Python)] 8983_사냥꾼 - 이분탐색

https://www.acmicpc.net/problem/8983

8983번: 사냥꾼

 

이 문제는 모든 사대에서 사격 가능한 영역을 구하고, 그 영역 안에 동물들이 있는지를 확인하는 방식으로 풀었을 때 시간복잡도가 O(M*N*L)이 소요됩니다. 비효율적이죠.

 

따라서 이분탐색을 통해 각 동물의 위치에서 가장 가까운 사대의 위치를 찾고 그 거리가 사정 거리 안에 있는지를 확인해주는 방식으로 문제를 풀었습니다.

 

각 동물의 위치에서 가장 가까운 사대의 위치는 x좌표가 가장 가까운 사대이기 때문에 findClosestNum()함수를 이용해서 사대 위치를 구해냈습니다(파이썬 내장 라이브러리인 bisect 함수를 이용하면 쉽게 구현할 수 있습니다).

 

그리고 각 동물의 위치에 대한 반복문을 수행하면서 해당 동물의 위치가 사냥 가능한 거리 안에 있는지 확인해주면 됩니다.

 

[풀이]

import sys
from bisect import bisect_left
input = sys.stdin.readline

# target과 가장 가까운 숫자를 리턴
def findClosestNum(array, target):
    index = bisect_left(array, target)
    if index == 0:
        return array[index]
    
    if index == len(array):
        return array[-1]

    left = array[index-1]
    right = array[index]

    if target-left < right - target:
        return left
    return right


m, n, l = map(int, input().split())
hunting_pos = sorted(list(map(int, input().split())))
animals = [tuple(map(int, input().split())) for _ in range(n)]

answer = 0
# 각 동물이 사냥될 수 있는 사대의 위치를 모아본다.
for x, y in animals:
    # 현재 동물의 위치에서 가장 가까운 사대 찾기
    closestHuntingPos = findClosestNum(hunting_pos, x)

    # 사대까지의 거리가 사정거리 안에 있는지 확인해본다.
    if x - (l-y) <= closestHuntingPos <= x + (l-y):
        answer += 1
        
print(answer)