[BOJ] 8983. 사냥꾼(이분탐색).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

우선 모든 동물과 모든 사대를 확인할 경우

O(M * N) = 10,000,000,000 이 되어서

Naive 한 방법으로는 해결할 수 없다.

처음에 생각한 방법은 사대를 기준으로 사정거리 안에 들어오는 동물을 찾으려고 했다.

이 방법은 최악의 경우 모든 사대를 확인하면서 모든 동물을 확인해야 했다. 

결국 시간복잡도는 O(M * N)...

계속 시도해보다가 해결방법이 떠오르지 않아 결국 힌트를 받게 되었다..

여기서 나는 생각의 전환이 필요하다는 것을 느꼈다.. 나에게도 아직 고정관념이 있다보다ㅠㅠ

사대에서만 사격이 가능하다고 하여 사대 기준으로만 생각했다는..

//

결정적인 힌트는 동물을 기준으로 생각하는 것이다.

각 동물은 자신을 잡을 수 있는 사대를 찾는다.

N 마리의 동물이 M 개의 사대 중 자신을 잡을 수 있는 사대 한 개만 찾으면 된다.

단, 자신을 잡을 수 있는 사대를 찾을 때 TLE(Time Limit Exceeded)를 해결하기 위해

이분 탐색을 활용해야 한다.

이분 탐색은 자신을 잡을 수 있는 사대를 찾기 위해 적용된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

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;     } Colored by Color Scripter

cs

이분 탐색을 활용할 경우 O(N * logM)에 해결할 수 있다.

이분 탐색 활용을 위해 사대의 위치를 정렬해주어야 할 것!

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;   public class BOJ8983 {       static int M, N, L, range[];     static Animal[] 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()); // 사정거리         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;         }     }   } Colored by Color Scripter

cs

#. Code_v2

더 최적화된 방법

해당 동물을 잡을 수 있는 사대 위치 범위를 먼저 구해준 후

범위에 포함되는 사대를 이분 탐색으로 찾는다.

(2,2), (5,1), (7,2) 위치에 있는 동물들의 경우

해당 동물을 잡을 수 있는 사대 위치 범위는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BOJ8983_v2 {
 
    static int M, N, L, range[];
    static Animal[] 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()); // 사정거리
        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++) {
            if(animals[i].c > L) continue;
            res += search(i);
        }
 
        return res;
    }
 
    // 이분탐색
    private static int search(int idx) {
        
        int start = 0, end = M - 1, mid = 0;
        int min = animals[idx].r + animals[idx].c - L;
        int max = animals[idx].r - animals[idx].c + L;
        
        while (start <= end) {
            mid = (start + end) / 2;
            
            if(min <= range[mid] && range[mid] <= max) return 1;
            else if(range[mid] < max) start = mid + 1;
            else end = mid - 1;
        }
        
        return 0;
    }
 
    static class Animal {
        int r, c;
 
        public Animal(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
 
}

line 60) 해당 동물을 잡을 수 있는 사대의 최소 범위

line 61) 해당 동물을 잡을 수 있는 사대의 최대 범위

line 63~69) 사대를 이분 탐색