[BAEKJOON_8983 - JAVA] 사냥꾼

문제

www.acmicpc.net/problem/8983

8983번: 사냥꾼

 

 

풀이

• 시간 제한이 1sec, 사대의수(100,000) * 동물의 수(100,000) → 1000억 TLE(시간초과 발생).
• 사대의 기준에서 탐색이 아닌 동물의 기준에서 가장 가까운 사대를 찾는 방식 사용.
• 과정의 4,5번이 많이 헷갈렸는데, 쉽게 이해 하자면 mid( = (left+right)/2 ) 중간값을 본인의 좌표쪽으로 계속 줄여나간다고 생각. 또는 본인의 값보다 작으면 본인과 크기가 같게 한다고 생각.(이해에 도움이 된다면 좋겠습니다.)

 

 

과정

1. 사대 정보를 받은 뒤 오름차순 정렬.
2. 모든 동물에 대해 이분탐색 진행.
3. 함수로 만든 사격 범위 판단 getDis를 활용.
4. 사정거리안에 사대가 없으며, 동물 기준 우측에 사대의 중간값(mid)이 위치하는 경우 left = mid+1
5. 사정거리안에 사대가 없으며, 동물 기준 좌측에 사대의 중간값(mid)이 위치하는 경우 right = mid-1
   (이해가 안간다면, 이분탐색의 개념을 다시 잡는걸 추천 / 급하다면 풀이의 3번째 항목 참고)
6. 사정거리 안에 사대가 있다면, 결과괎++

알고리즘 지식

• 이분 탐색
• 정렬

 

 

JAVA코드

package BaekJoon_2020_12_22__23;

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

/**
 * @packageName : BaekJoon_2020_12_22
 * @fileName : BJ_8983_사냥꾼.java
 * @author : Mingeon
 * @date : 2020. 12. 23.
 * @language : JAVA
 * @classification : 이분탐색
 * @time_limit : 1sec
 * @required_time : 07:22 ~ 19:39
 * @submissions : 1
 * @description
 * 1. 기준점을 동물기준으로 잡아야한다.
 * 2. 효율을 위한 이분탐색.
 * 2-1 범위를 벗어나며, 동물기준 좌측에 중간값의 사대가 위치하는 경우 -> left = mid+1
 * 2-2 범위를 벗어나며, 동물기준 우측에 중간값의 사대가 위치하는 경우 -> right = mid-1
 */

public class BJ_8983_사냥꾼 {

	static int M; // 사대의 수
	static int N; // 동물의 수
	static int L; // 사정거리
	static int[] MPos; // 사대 좌표
	static ArrayList<Animals> animals; // 동물들의 좌표

	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 = Integer.parseInt(st.nextToken()); // 사정거리

		// 사대 정보
		MPos = new int[M];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			MPos[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(MPos);

		// 동물 정보
		animals = new ArrayList<Animals>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int col = Integer.parseInt(st.nextToken());
			int row = Integer.parseInt(st.nextToken());
			animals.add(new Animals(row, col));
		} // End of input

		int ret = process();
		System.out.println(ret);
	}

	private static int process() {
		int ret = 0;

		for (int i = 0; i < N; i++) {
			ret += search(i);
		}

		return ret;
	}

	// 이분 탐색
	private static int search(int idx) {

		int left = 0;
		int right = M;
		int mid = 0;

		while (left <= right) {
			mid = (left + right) / 2;
			// 범위 초과
			if (mid >= M) {
				return 0;
			}

			// 사정거리
			int dist = getDis(MPos[mid], animals.get(idx));

			// 사정거리 범위를 벗어나며, 동물이 사대의 중간값보다 좌측에 위치한 경우
			if ((L < dist) && animals.get(idx).col < MPos[mid]) {
				right = mid - 1;
			}

			// 사정거리 범위를 벗어나며, 동물이 사대의 중간값보다 우측에 위치한 경우
			else if (L < dist && animals.get(idx).col >= MPos[mid]) {
				left = mid + 1;
			}
			// 사정거리 안에 들어올 경우
			else if (L >= dist) {
				return 1;
			}
		}

		return 0;
	}

	// 사격 범위에 포함 판단
	private static int getDis(int x, Animals animal) {
		return (Math.abs(x - animal.col) + animal.row);
	}

}

class Animals {
	int row;
	int col;

	public Animals(int row, int col) {
		this.row = row;
		this.col = col;
	}

}