백준 8983번

접근 방식 (알고리즘 분류)

• 이진탐색

내풀이

from bisect import bisect_left, bisect_right
import sys

input = sys.stdin.readline

m, n, l = map(int, input().split())
sade = list(map(int, input().split()))
sade.sort()
check_x, check_y = [], []
for i in range(n):
    x, y = map(int,input().split())
    check_x.append(x)
    check_y.append(y)

result = 0
for point in range(n):
    tmp = bisect_left(sade, check_x[point])
    flag = 0
    # 사대의 젤 마지막 위치보다 클때
    if check_x[point] >= sade[-1]:
        if abs(sade[-1] - check_x[point]) + check_y[point] <= l:
            result += 1
        continue

    # 사대의 사이에 있을때
    if abs(check_x[point] - sade[tmp-1]) < abs(check_x[point] - sade[tmp]):
        if abs(sade[tmp-1] - check_x[point]) + check_y[point] <= l:
            result += 1
    elif abs(check_x[point] - sade[tmp-1]) >= abs(check_x[point] - sade[tmp]):
        if abs(sade[tmp] - check_x[point]) + check_y[point] <= l:
            result += 1

print(result)

풀이 설명

• 크게 두가지 경우로 구분
  1. 타겟이 맨 뒤의 사대보다 뒤에 위치할 경우 --> 맨 뒤의 사대만 고려해주면 된다. --> index 에러 방지
  2. 타겟이 사대 사이에 있을 경우 --> bisect_left로 찾은 위치와 그 앞의 위치준에서 타겟과 가까운 위치로 설정해야 된다.

느낀점

• N의 범위를 보면 10만이상인 것을 알 수 있다.
• python은 1초당 2000만번의 연산을 수행한다.
• 그렇기 때문에 N*2으로는 문제를 해결할 수 없기때문에 완전탐색으로 접근하면 풀 수 없다.
• 따라서 100000*log100000 = 100000 X 5 = 500000이므로 NlogN으로는 접근이 가능하다. --> 이진탐색