문제
x축 위에 M개의 사대가 있고, 2차원 평면에 N마리의 동물이 있다. 사정거리 L 이내(맨해튼 거리)인 동물을 잡을 수 있을 때, 잡을 수 있는 동물 수를 구하라.
입력
첫째 줄에 M, N, L이 주어진다. 둘째 줄에 사대 위치, 이후 N줄에 동물 좌표가 주어진다.
출력
잡을 수 있는 동물 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 8 4 6 1 4 9 7 2 3 3 4 5 5 1 2 2 1 4 8 4 9 4 | 6 |
풀이
사대를 정렬한 뒤, 각 동물에 대해 이분 탐색으로 잡을 수 있는지 판단한다.
- 사대를 오름차순 정렬한다
- 각 동물 (a, b)에 대해 사대 배열에서 이분 탐색을 수행한다
- 맨해튼 거리
|x - a| + b가 L 이하인 사대가 있는지 확인한다 - 동물이 사대보다 왼쪽이면 탐색 범위를 좁히고, 오른쪽이면 넓힌다
- 거리 L 이내 사대가 존재하면 카운트한다
핵심 아이디어: 사대가 x축 위에 있으므로 맨해튼 거리는 |x - a| + b이다. 정렬된 사대에서 이분 탐색으로 가장 가까운 사대를 O(log M)에 찾는다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Day347BOJ8983사냥꾼 {
static int M, N, L, range[];
static Animal[] animals;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken()); // 사대의 수
N = Integer.parseInt(st.nextToken()); // 동물의 수
L = Integer.parseInt(st.nextToken()); // 사정거리
range = new int[M];
animals = new Animal[N];
// 사대 정보
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
range[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
animals[i] = new Animal(a, b);
}
System.out.println(process());
}
private static int process() {
int res = 0;
Arrays.sort(range);
for (int i = 0; i < N; i++) {
res += search(i);
}
return res;
}
private static int search(int idx) {
int start = 0, end = M, mid = 0;
while (start <= end) {
mid = (start + end) / 2;
if (mid >= M)
return 0;
int dist = getDist(animals[idx].r, animals[idx].c, range[mid]);
if (L < dist && animals[idx].r < range[mid])
end = mid - 1;
else if (L < dist && animals[idx].r >= range[mid])
start = mid + 1;
else if (L >= dist)
return 1;
}
return 0;
}
private static int getDist(int a, int b, int x) {
return Math.abs(x - a) + b;
}
static class Animal {
int r, c;
public Animal(int r, int c) {
this.r = r;
this.c = c;
}
}
}복잡도
- 시간: O((M + N) log M) - 사대 정렬 + 동물당 이분 탐색
- 공간: O(M + N)