[ 백준 - 8983 ] 사냥꾼

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

8983번: 사냥꾼

처음 풀 때도 참고해서 풀었고, 다시 풀 때도 참고해서 풀었다.

이분 탐색 문제들을 마주하면 가장 안되는게 이분 탐색 알고리즘 자체는 간단한거 같은데, 적재적소에 사용하는게 힘든거 같다.

 

문제 조건만 보면 사대 100,000 x 동물의 수 100,000 이기 때문에 완전 탐색 방식으로는 주어진 시간 제한을 만족할 수 없다는건 알 수 있었다.

---

[ 📌 풀이 ]

• 동물과 사대간의 거리를 구하는 공식 |x - a| + b
• 사대에서 동물을 사냥할 수 없는 조건은 위 공식보다 결과보다 사정거리가 짧은 경우이다.
• 모든 동물에 대해서 사냥이 가능한지 확인이 필요하다.
• 사대의 경우 sorting이 되지 않은 상태로 input 이 들어오기 때문에 sorting 해야한다.

[ 사대 이미지 ]

• 사대의 최대 사거리 이상의 높이에 있는 동물은 어느 사대에서도 잡을 수 없다.

동물이 잡힐 수 있다는 정보만 알게 되면 더 이상 서칭은 진행할 필요 없기 때문에 동물을 타겟으로 잡고 사대 배열을 이분 탐색해서 동물을 잡을 수 있는 사대를 찾은 후 찾게 된다면 다음 동물을 진행하면 된다.

---

[ 📌 코드 - Python (정글 과정 중 풀이) ]

import sys

M, N, L = map(int, sys.stdin.readline().split())
hunters = list(map(int, sys.stdin.readline().split()))
hunters.sort()
animals = []
count = 0

for _ in range(N):
    x, y = map(int, sys.stdin.readline().split())
    animals.append((x, y))

def binarySearch(x, y):
    global left, right

    while left <= right:
        mid = (left + right) // 2   # 사격 하는 포대 인덱스

        if abs(hunters[mid] - x) + y <= L:
            return True

        if hunters[mid] - x < 0:
            left = mid + 1
        else:
            right = mid - 1

for idx, animal in enumerate(animals):
    left, right = 0, len(hunters) - 1

    if binarySearch(animal[0], animal[1]):
        count += 1

print(count)

[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.12.25(Mon)
# Spend Time: 52m 37s
# Runtime   : 42352 KB
# Memory    : 816 ms
# Algoritm  : Binary Search
"""

import sys
inp = sys.stdin.readline

M, N, L = map(int, inp().split())
loc = list(map(int, inp().split()))
loc.sort()
animals = []

cnt = 0

for idx in range(N):
  l, r = 0, len(loc) - 1
  x, y = map(int, inp().split())

  while l <= r:
    mid = (l + r) // 2

    if abs(loc[mid] - x) + y <= L:
      cnt += 1
      break

    if loc[mid] - x > 0:
      r = mid - 1
    else:
      l = mid + 1

print(cnt)

[ 📌 코드 - Java ]

/**
* Author    : Lee In Bok 
* Date      : 2023.12.25(Mon)
* Spend Time: 52m 37s
* Runtime   : 58612 KB
* Memory    : 712 ms
* Algoritm  : Binary Search
 */

package BaekJoon.BinarySearch.Q8983;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q8983 {
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int M = Integer.parseInt(st.nextToken());
    int N = Integer.parseInt(st.nextToken());
    int L = Integer.parseInt(st.nextToken());
    int[] loc = Arrays.stream(br.readLine().split(" "))
                                           .mapToInt(Integer::parseInt)
                                           .sorted()
                                           .toArray();
    int cnt = 0; 

    for(int i = 0; i < N; i++){
      st = new StringTokenizer(br.readLine());
      int x = Integer.parseInt(st.nextToken());
      int y = Integer.parseInt(st.nextToken());
      int l = 0;
      int r = M - 1;

      while(l <= r){
        int mid = (l + r) / 2;
        int gap = loc[mid] - x;

        if(Math.abs(gap) + y <= L){
          cnt++;
          break;
        }

        if(gap > 0){
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
    }

    System.out.println(cnt);
  }
}

---

[ 📌 결과 - Python & Java ]

[ Result - Python & Java ]