백준 - 8983 사냥꾼 [이분탐색]

8983 사냥꾼

 

1. 문제유형

• 이분탐색, 정렬

2. 자료구조

• m (int): 사대의 수
• n (int): 동물의 수
• l (int): 사대 사정거리
• gun (list): 사대 좌표를 담은 리스트
• animal (list): 동물 좌표를 담은 리스트
• cnt (int): 잡은 동물의 수
• s (int): 해당 동물을 잡을 수 있는 최소 사대 좌표
• e (int): 해당 동물을 잡을 수 있는 최대 사대 좌표
• left, right(int): 사대 좌표의 최소값(0), 최대값(m-1) 인덱스
• mid (int): 동물을 잡을 수 있는 사대 좌표값 (left+right)//2

3. 해결과정

• ⭐ 사대 거리를 고정하고 가능한 동물 수를 구하려고 하면 시간 복잡도가 높아진다. (n^2)
• ⭐ 따라서 동물을 고정하고, 잡을 수 있는 사대가 존재하는 지 확인하는 하는 것이 쉽다. (nlogn)
• ⭐ 동물을 잡을 수 있는 사대 좌표는 s = x+y-l (최소값) ~ e = x-y+l 이다. (l 최대 범위가 크기 때문)
• 사대 좌표를 담은 리스트를 이분탐색할 것이므로 정렬 후 수행한다.

1. x, y좌표별로 s, e를 계산한다.
2. left, right 지정 후 left<=right 동안 mid값이 s와 e 사이에 속하는 지 체크한다.
3. 반복문 조기 종료 조건은 y가 l보다 큰 경우이다. 이 경우 동물을 잡을 수 없다.
4. 해당 구간에 mid가 속한다면 cnt를 증가시킨 후 반복문을 탈출한다.
5. mid가 s보다 작다면 left = mid + 1
6. mid가 s보다 크다면 right = mid - 1

4. 소스코드

import sys

m, n, l = map(int, input().split())
gun = list(map(int, sys.stdin.readline().split()))
animal = list(map(int, sys.stdin.readline().split()) for _ in range(n))
gun.sort()
cnt = 0

for x, y in animal:
    if (y>l):
        continue
    s = x+y-l
    e = x-y+l
    left, right = 0, m-1
    while left <= right:
        mid = (left+right)//2
        if gun[mid] >= s and gun[mid] <= e:
            cnt += 1
            break
        elif gun[mid] < e:
            left = mid + 1
        else:
            right = mid - 1
print(cnt)