사냥꾼/8983/파이썬/이분탐색

I1:
4 8 4
6 1 4 9
7 2
3 3
4 5
5 1
2 2
1 4
8 4
9 4

O1 :
6

I2 :
1 5 3
3
2 2
1 1
5 1
4 2
3 3

O2:
5

import sys
from bisect import bisect_left

M, N, L = map(int, sys.stdin.readline().split())
guns = sorted(list(map(int, sys.stdin.readline().split())))
beasts = list(list(map(int, sys.stdin.readline().split())) for _ in range(N))
count = 0
idx = 0

for i in range(N):
    a, b = beasts[i][0], beasts[i][1]
    idx = bisect_left(guns, a)
    if idx > M - 1:
        idx -= 1
    if abs(guns[idx] - a) + b <= L or abs(guns[idx - 1] - a) + b <= L:
        count += 1
print(count)

포인트는 최적화, bisect left 는 같은 수일 경우 왼쪽에 출력한다. (원래 그 숫자위치의 인덱스를 리턴)

가장 가까이 있는 사대와의 거리를 확인해야돼서, idx -1 과 idx 값을 확인해줘야댐

만약 최댓값보다 클 경우는 오른쪽에 출력하므로 index 를 넘어가게 된다. 이 경우 idx - 1 만 해주면 된다.

조건을 많이 달 경우 통과를 못한다(beast sorting 불필요, a,b 따로 변수에 저장해서 최대한 줄임)