[알고리즘] 백준 11663 선분 위의 점 - JAVA

www.acmicpc.net/problem/11663

11663번: 선분 위의 점

문제 설명

1차원 상의 좌표와 선분이 주어진다.

 

선분에 올라갈 수 있는 점의 개수를 구하는 문제이다.

 

해결방법

이분탐색을 두 번 돌려서 해결했다.

 

선분의 좌표를 (x,y)라고 할 때,

 

x를 기준으로 좌표에 대해 이분탐색을 돌려 x를 포함한 오른쪽 부분의 인덱스

 

y를 기준으로 좌표에 대해 이분탐색을 돌려 y를 포함한 왼쪽 부분의 인덱스

 

이 두개를 구하면 y - x를 통해 점으로 주어진 좌표상에서 선분 사이에 있는 점의 개수를 구할 수 있다.

 

 

소스코드

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

class Main {

    static int n;
    static int m;
    static long[] dot;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        dot = new long[n];
        s = br.readLine();
        st = new StringTokenizer(s, " ");

        for (int i = 0; i < n; i++) {
            dot[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(dot);

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < m; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");
            int result = binarySearch(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            sb.append(result).append('\n');
        }

        System.out.println(sb.toString().trim());

    }

    static int binarySearch(int x, int y) {
        int left = 0;
        int right = dot.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (dot[mid] > y) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        int endIndex = right + 1;

        left = 0;
        right = dot.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (dot[mid] < x) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        int startIndex = left;

//        System.out.println("페어 : " + startIndex + " " + endIndex);

        return endIndex - startIndex;
    }

}