백준 : 8983 사냥꾼

Y정렬을 생각하다가 가장 중요한걸 생각하지못해다.

 

문제의 아이디어는 Animal 의 x 위치기준으로 좌 우에 있는 사대만 검사하면된다.

 

이때 Animal을 x기준으로 정렬한다면 사대위치를 다시 뒤로 볼필요가없다.

 

따라서 Animal.x를 기준으로 왼쪽에서 가장 가까운 사대위치를 찾고 왼쪽사대와 오른쪽 사대 길이를 비교해서 반환한다.

 

package 삼성;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class 사냥꾼 {
	static class Map implements Comparable<Map> {
		long y;
		long x;

		public Map(long y, long x) {
			super();
			this.y = y;
			this.x = x;
		}

		@Override
		public int compareTo(Map o) {
			if (y > o.y) {
				return 1;
			} else if (y == o.y) {
				return Long.compare(x, o.x);
			}
			return -1;
		}
	}

	static TreeSet<Map> candidate = new TreeSet<>();
	static ArrayList<Map> animal = new ArrayList<>();
	static Map[] human;
	static int M, N;
	static long L;

	public static void main(String[] args) throws IOException {
		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 = Long.parseLong(st.nextToken());
		human = new Map[M];
		st = new StringTokenizer(br.readLine());

		for (int m = 0; m < M; m++) {
			human[m] = new Map(0, Long.parseLong(st.nextToken()));
		}
		Arrays.sort(human,new cmp());
		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			long x = Long.parseLong(st.nextToken());
			long y = Long.parseLong(st.nextToken());
			if (y > L)
				continue;
			animal.add(new Map(y, x));
		}

		Collections.sort(animal, new cmp());

		int pivot = 0;

		// animal 후보군
		long ans = 0L;
		for (int n = 0; n < animal.size(); n++) {
			Map cur = animal.get(n);
			while (pivot + 1 < M && human[pivot + 1].x <= cur.x) {
				pivot++;
			}

			// 직전 피봇
			// 되면 ++
			if (Dis(human[pivot], cur) <= L) {
				ans++;
				continue;
			} else if (pivot + 1 < M && Dis(human[pivot + 1], cur) <= L) {
				ans++;
				continue;
			}
		}

		System.out.println(ans);

	}

	public static class cmp implements Comparator<Map> {

		@Override
		public int compare(Map o1, Map o2) {
			if (o1.x > o2.x) {
				return 1;
			} else if (o1.x == o2.x) {
				return Long.compare(o1.y, o2.y);
			}
			return -1;
		}

	}

	static long Dis(Map a, Map b) {

		return Math.abs(a.y - b.y) + Math.abs(a.x - b.x);
	}

}